Submission #330229


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 1049 ms
Memory 118820 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
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
WA × 1
MLE × 1
MLE × 1
WA × 1
WA × 1
MLE × 1
MLE × 1
RE × 1
RE × 1
RE × 1
MLE × 1
RE × 1
MLE × 1
TLE × 1
MLE × 1
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 43 ms 5728 KB
02 WA 30 ms 2468 KB
03 WA 30 ms 2856 KB
04 WA 29 ms 2344 KB
05 WA 41 ms 5788 KB
06 WA 45 ms 6948 KB
07 MLE 630 ms 118316 KB
08 MLE 704 ms 117928 KB
09 WA 66 ms 10724 KB
10 WA 65 ms 10664 KB
11 MLE 360 ms 31524 KB
12 MLE 353 ms 31576 KB
13 RE 326 ms 13840 KB
14 RE 371 ms 1568 KB
15 RE 326 ms 1568 KB
16 MLE 204 ms 32296 KB
17 RE 303 ms 1316 KB
18 MLE 753 ms 97312 KB
19 TLE 1049 ms 118724 KB
20 MLE 663 ms 118820 KB