답안 #31008 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
31008	2017-08-04T00:44:14 Z	kajebiii	정렬하기 (IOI15_sorting)	C++14	100 / 100	528 ms	13816 KB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef unsigned long long ull;
typedef pair<double, double> pd;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 2e5 + 100;

int N, M, *S, *X, *Y, *P, *Q;
int Now[MAX_N], To[MAX_N], NowR[MAX_N], ToR[MAX_N];
int sortIx;
bool isSort() {
    while(sortIx < N && NowR[sortIx] == ToR[sortIx]) sortIx++;
//    printf("sortIx : %d\n", sortIx);
    return sortIx == N;
}
bool isCan(int m) {
    sortIx = 0;
    for(int i=0; i<N; i++) Now[i] = S[i], To[i] = i;
    for(int i=0; i<N; i++) NowR[Now[i]] = i, ToR[To[i]] = i;
    for(int i=m-1; i>=0; i--) {
        int x = X[i], y = Y[i];
        swap(ToR[To[x]], ToR[To[y]]);
        swap(To[x], To[y]);
    }
    for(int i=0; i<m; i++) P[i] = 0, Q[i] = 0;
    
//    printf("%d start\n", m);
//    printf("N : "); for(int i=0; i<N; i++) printf("%d ", Now[i]); puts("");
//    printf("T : "); for(int i=0; i<N; i++) printf("%d ", To[i]);  puts("");
    if(isSort()) return true;
    for(int i=0; i<m; i++) {
        int x = X[i], y = Y[i];
        swap(ToR[To[x]], ToR[To[y]]);
        swap(To[x], To[y]);
        swap(NowR[Now[x]], NowR[Now[y]]);
        swap(Now[x], Now[y]);

        int l = NowR[sortIx], r = ToR[sortIx];
        swap(NowR[Now[l]], NowR[Now[r]]);
        swap(Now[l], Now[r]);
        P[i] = l; Q[i] = r;
//        printf("N : "); for(int i=0; i<N; i++) printf("%d ", Now[i]); puts("");
//        printf("T : "); for(int i=0; i<N; i++) printf("%d ", To[i]);  puts("");
        if(isSort()) return true;
    }
    return false;
}
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    N = n; M = m; S = s; X = x; Y = y; P = p; Q = q;
    int ans = -1;
    for(int l=0, r=M; l<=r; ) {
        int m = (l+r) >> 1;
        if(isCan(m)) ans = m, r = m-1; else l = m+1;
    }
    isCan(ans);
    return ans;
}

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:66:13: warning: declaration of 'int m' shadows a parameter [-Wshadow]
         int m = (l+r) >> 1;
             ^
sorting.cpp:62:39: note: shadowed declaration is here
 int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
                                       ^

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	512 KB	Output is correct
2	Correct	5 ms	512 KB	Output is correct
3	Correct	4 ms	512 KB	Output is correct
4	Correct	3 ms	512 KB	Output is correct
5	Correct	3 ms	512 KB	Output is correct
6	Correct	3 ms	512 KB	Output is correct
7	Correct	3 ms	512 KB	Output is correct
8	Correct	3 ms	512 KB	Output is correct
9	Correct	4 ms	512 KB	Output is correct
10	Correct	4 ms	512 KB	Output is correct
11	Correct	4 ms	512 KB	Output is correct
12	Correct	3 ms	512 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	320 ms	12408 KB	Output is correct
16	Correct	438 ms	12664 KB	Output is correct
17	Correct	527 ms	13240 KB	Output is correct
18	Correct	99 ms	10488 KB	Output is correct
19	Correct	259 ms	12372 KB	Output is correct
20	Correct	283 ms	12536 KB	Output is correct
21	Correct	244 ms	12664 KB	Output is correct
22	Correct	298 ms	13432 KB	Output is correct
23	Correct	294 ms	13688 KB	Output is correct
24	Correct	528 ms	13560 KB	Output is correct
25	Correct	455 ms	13304 KB	Output is correct
26	Correct	370 ms	12536 KB	Output is correct
27	Correct	321 ms	12280 KB	Output is correct
28	Correct	460 ms	13432 KB	Output is correct
29	Correct	353 ms	13148 KB	Output is correct
30	Correct	265 ms	11768 KB	Output is correct
31	Correct	493 ms	13432 KB	Output is correct
32	Correct	294 ms	13304 KB	Output is correct
33	Correct	498 ms	13560 KB	Output is correct
34	Correct	340 ms	13520 KB	Output is correct
35	Correct	249 ms	12152 KB	Output is correct
36	Correct	61 ms	11256 KB	Output is correct
37	Correct	460 ms	13816 KB	Output is correct
38	Correct	344 ms	13304 KB	Output is correct
39	Correct	412 ms	13432 KB	Output is correct

답안 #31008

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