Submission #330227
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define lli long long int
#define pii pair<int,int>
#define mod 1000000007
#define N (int)1e6+10
#define mp make_pair
#define pb push_back
#define nd second
#define st first
#define endl '\n'
#define inf mod
#define sag (sol|1)
#define sol (root<<1)
#define ort ((bas+son)>>1)
vector< pii > a1,a2;
int x,y,n,m,i,j,k;
int mn = 1000000,ans1,ans2;
int dp[5005][5005];
int H[5005][5005];
bool cmp(pii x,pii y){
if(x.nd < y.nd)
return 1;
return 0;
}
int main(){
cin >> n >> m;
for(i=1 ; i<=n ; i++){
cin >> x >> y;
a1.pb(mp(x,i));
a2.pb(mp(y,i));
}
sort(a1.begin(),a1.end());
sort(a2.begin(),a2.end());
for(i=0 ; i<n ; i++){
a1[i].st = i+1;
a2[i].st = i+1;
}
sort(a1.begin(),a1.end(),cmp);
sort(a2.begin(),a2.end(),cmp);
for(i=0 ; i<n ; i++){
H[a1[i].st][a2[i].st] = 1;
}
for(i=1 ; i<=n ; i++)
for(j=1 ; j<=n ; j++)
dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + H[i][j];
for(i=0 ; i<n ; i++)
for(j=0 ; j<n ; j++){
int x1 = a1[i].st; int y1 = a2[i].st;
int x2 = a1[j].st; int y2 = a2[j].st;
if(x1 < x2) swap(x1,x2);
if(y1 < y2) swap(y1,y2);
int t = dp[x1][y1] + dp[x2][y2] - dp[x1][y2] - dp[x2][y1] + 1;
if(t>=m and mn>t){
mn = t;
ans1 = i+1;
ans2 = j+1;
}
}
cout << ans1 << ' ' << ans2 << endl;
}
Submission Info
Submission Time |
|
Task |
2 - Artemis |
User |
ykaya |
Language |
C++ (G++ 4.6.4) |
Score |
0 |
Code Size |
1681 Byte |
Status |
WA |
Exec Time |
1054 ms |
Memory |
118984 KB |
Judge Result
Set Name |
Set01 |
Set02 |
Set03 |
Set04 |
Set05 |
Set06 |
Set07 |
Set08 |
Set09 |
Set10 |
Set11 |
Set12 |
Set13 |
Set14 |
Set15 |
Set16 |
Set17 |
Set18 |
Set19 |
Set20 |
Score / Max Score |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
0 / 5 |
Status |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Set Name |
Test Cases |
Set01 |
01 |
Set02 |
02 |
Set03 |
03 |
Set04 |
04 |
Set05 |
05 |
Set06 |
06 |
Set07 |
07 |
Set08 |
08 |
Set09 |
09 |
Set10 |
10 |
Set11 |
11 |
Set12 |
12 |
Set13 |
13 |
Set14 |
14 |
Set15 |
15 |
Set16 |
16 |
Set17 |
17 |
Set18 |
18 |
Set19 |
19 |
Set20 |
20 |
Case Name |
Status |
Exec Time |
Memory |
01 |
WA |
52 ms |
5836 KB |
02 |
WA |
34 ms |
2568 KB |
03 |
WA |
34 ms |
3080 KB |
04 |
WA |
34 ms |
2448 KB |
05 |
WA |
52 ms |
5824 KB |
06 |
WA |
55 ms |
7108 KB |
07 |
MLE |
719 ms |
118344 KB |
08 |
MLE |
829 ms |
118032 KB |
09 |
WA |
78 ms |
10780 KB |
10 |
WA |
75 ms |
10824 KB |
11 |
MLE |
367 ms |
31556 KB |
12 |
MLE |
360 ms |
31560 KB |
13 |
RE |
328 ms |
13896 KB |
14 |
RE |
324 ms |
1600 KB |
15 |
RE |
318 ms |
1604 KB |
16 |
MLE |
253 ms |
32456 KB |
17 |
RE |
314 ms |
1372 KB |
18 |
MLE |
961 ms |
97424 KB |
19 |
TLE |
1054 ms |
118984 KB |
20 |
MLE |
767 ms |
118924 KB |