답안 #137427

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
137427	2019-07-27T17:52:29 Z	Runtime_error_	정렬하기 (IOI15_sorting)	C++14	100 / 100	693 ms	28280 KB

sorting

//100 points
#include "sorting.h"
#include <bits/stdc++.h>
#define mid (l+r)/2
using namespace std;
const int inf = 6e5+9;
int n,m,x[inf],y[inf],a[inf],pos[inf],from[inf],origin[inf],posfrom[inf];

bool check(int i,int p[],int q[]){

        int l = 0,notvalid = 0;
        for(int j=0;j<n;j++){
            from[j] = j;
            a[j] = origin[j];
            p[j] = q[j] = 0;
            pos[ a[j] ] = j;
            posfrom[ from[j] ] = j;
            notvalid += (a[j] != j);
        }
        //cout<<i<<" "<<notvalid<<endl;
         for(int j=i;j>=0;j--){
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);
            swap( from[ x[j] ] , from[ y[j] ] );
        }

        for(int j=0;j<=i;j++){

            swap(pos[ a[ x[j] ] ] , pos[ a[ y[j] ] ]);
            swap(posfrom[ from[ x[j] ] ] , posfrom[ from[ y[j] ] ]);

            notvalid -= (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
            swap(a[ x[j] ] , a[ y[j] ] );
            notvalid += (a[ x[j] ] != x[j]) + (a[ y[j] ] != y[j]);
            swap(from[ x[j] ] , from[ y[j] ]);

            //cout<<notvalid<<" ";
            int idx,idfrom;

            while(l<n){
                idx = pos[l];
                idfrom = posfrom[l];
                if(idx != idfrom)
                    break;
                l++;
            }
            swap(pos[ a[ idx ] ] , pos[ a[ idfrom ] ]);
            notvalid -= (a[idx] != idx) + (a[idfrom] != idfrom);
            swap(a[idx],a[idfrom]);
            notvalid += (a[idx] != idx) + (a[idfrom] != idfrom);

            //cout<<notvalid<<" ";
            //cout<<l<<" "<<idx<<" "<<idfrom<<endl;
            //cout<<"swap "<<idx<<" "<<idfrom<<endl;
            p[j] = idx,q[j] = idfrom;
            if(notvalid == 0)
                return 1;
        }
        //for(int i=0;i<n;i++)
        //    cout<<a[i]<<" ";
        return 0;
}

int findSwapPairs(int N, int A[], int M, int X[], int Y[], int p[], int q[]){
    n = N;
    m = M;
    bool tr = 1;
    for(int i=0;i<n;i++){
        a[i] = A[i];
        pos[ a[i] ] = i;
        origin[i] = a[i];
        if(a[i] != i)
            tr = 0;
    }
    if(tr)
        return 0;

    for(int i=0;i<m;i++)
        x[i] = X[i],y[i] = Y[i];

    int l = 0 , r = m-1;
    while(r-l>1){
        if(check(mid,p,q))
            r = mid;
        else
            l = mid;
    }
    if(check(0,p,q))
        r = 0;
    check(r,p,q);
    return r+1;
}

Subtask #1
8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	424 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct

Subtask #2
12.0 / 12.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	424 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	296 KB	Output is correct
9	Correct	2 ms	276 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct

Subtask #3
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	504 KB	Output is correct
6	Correct	2 ms	380 KB	Output is correct

Subtask #4
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	424 KB	Output is correct
7	Correct	2 ms	380 KB	Output is correct
8	Correct	2 ms	296 KB	Output is correct
9	Correct	2 ms	276 KB	Output is correct
10	Correct	3 ms	376 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	2 ms	376 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	2 ms	504 KB	Output is correct
16	Correct	2 ms	376 KB	Output is correct
17	Correct	2 ms	504 KB	Output is correct
18	Correct	2 ms	380 KB	Output is correct
19	Correct	2 ms	376 KB	Output is correct
20	Correct	2 ms	376 KB	Output is correct
21	Correct	4 ms	760 KB	Output is correct
22	Correct	3 ms	760 KB	Output is correct
23	Correct	4 ms	764 KB	Output is correct
24	Correct	4 ms	808 KB	Output is correct
25	Correct	4 ms	760 KB	Output is correct
26	Correct	3 ms	764 KB	Output is correct
27	Correct	4 ms	760 KB	Output is correct

Subtask #5
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	4 ms	632 KB	Output is correct
3	Correct	4 ms	632 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	632 KB	Output is correct
9	Correct	4 ms	632 KB	Output is correct
10	Correct	4 ms	632 KB	Output is correct
11	Correct	4 ms	636 KB	Output is correct
12	Correct	4 ms	632 KB	Output is correct
13	Correct	4 ms	632 KB	Output is correct
14	Correct	3 ms	632 KB	Output is correct

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	504 KB	Output is correct
2	Correct	4 ms	632 KB	Output is correct
3	Correct	4 ms	632 KB	Output is correct
4	Correct	2 ms	508 KB	Output is correct
5	Correct	3 ms	632 KB	Output is correct
6	Correct	3 ms	632 KB	Output is correct
7	Correct	3 ms	632 KB	Output is correct
8	Correct	4 ms	632 KB	Output is correct
9	Correct	4 ms	632 KB	Output is correct
10	Correct	4 ms	632 KB	Output is correct
11	Correct	4 ms	636 KB	Output is correct
12	Correct	4 ms	632 KB	Output is correct
13	Correct	4 ms	632 KB	Output is correct
14	Correct	3 ms	632 KB	Output is correct
15	Correct	359 ms	24180 KB	Output is correct
16	Correct	496 ms	25444 KB	Output is correct
17	Correct	693 ms	26860 KB	Output is correct
18	Correct	47 ms	15612 KB	Output is correct
19	Correct	334 ms	26360 KB	Output is correct
20	Correct	364 ms	27000 KB	Output is correct
21	Correct	356 ms	26972 KB	Output is correct
22	Correct	369 ms	21624 KB	Output is correct
23	Correct	410 ms	27896 KB	Output is correct
24	Correct	643 ms	27388 KB	Output is correct
25	Correct	652 ms	27160 KB	Output is correct
26	Correct	449 ms	27000 KB	Output is correct
27	Correct	418 ms	26232 KB	Output is correct
28	Correct	598 ms	27384 KB	Output is correct
29	Correct	601 ms	27000 KB	Output is correct
30	Correct	323 ms	25848 KB	Output is correct
31	Correct	593 ms	27516 KB	Output is correct
32	Correct	435 ms	26564 KB	Output is correct
33	Correct	662 ms	27648 KB	Output is correct
34	Correct	558 ms	27452 KB	Output is correct
35	Correct	339 ms	25848 KB	Output is correct
36	Correct	90 ms	24568 KB	Output is correct
37	Correct	556 ms	28280 KB	Output is correct
38	Correct	539 ms	27128 KB	Output is correct
39	Correct	554 ms	27360 KB	Output is correct

답안 #137427

Compilation message

Subtask #1 8.0 / 8.0

Subtask #2 12.0 / 12.0

Subtask #3 16.0 / 16.0

Subtask #4 18.0 / 18.0

Subtask #5 20.0 / 20.0

Subtask #6 26.0 / 26.0

Subtask #1
8.0 / 8.0

Subtask #2
12.0 / 12.0

Subtask #3
16.0 / 16.0

Subtask #4
18.0 / 18.0

Subtask #5
20.0 / 20.0

Subtask #6
26.0 / 26.0