Submission #330245
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];
int sa[5005];
int su[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++){
sa[a1[i].st] = a2[i].st;
su[a2[i].st] = a1[i].st;
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-1] - dp[x2-1][y1] - 1 ;
if(sa[x2] < y2) t--;
if(su[y2] < x2) t--;
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 |
1854 Byte |
Status |
WA |
Exec Time |
1052 ms |
Memory |
118968 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 |
51 ms |
5992 KB |
02 |
WA |
31 ms |
2616 KB |
03 |
WA |
32 ms |
3000 KB |
04 |
WA |
30 ms |
2484 KB |
05 |
WA |
47 ms |
5952 KB |
06 |
WA |
50 ms |
7100 KB |
07 |
MLE |
711 ms |
118456 KB |
08 |
MLE |
826 ms |
118072 KB |
09 |
WA |
74 ms |
10808 KB |
10 |
WA |
76 ms |
10804 KB |
11 |
MLE |
364 ms |
31784 KB |
12 |
MLE |
354 ms |
31672 KB |
13 |
RE |
329 ms |
14140 KB |
14 |
RE |
304 ms |
1772 KB |
15 |
RE |
311 ms |
1720 KB |
16 |
MLE |
254 ms |
32472 KB |
17 |
RE |
353 ms |
1480 KB |
18 |
MLE |
998 ms |
97468 KB |
19 |
TLE |
1052 ms |
118968 KB |
20 |
MLE |
738 ms |
118968 KB |