답안 #318033

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318033	2020-10-31T09:32:47 Z	wildturtle	정렬하기 (IOI15_sorting)	C++14	100 / 100	380 ms	25172 KB

sorting

#include <bits/stdc++.h>
#include "sorting.h"
using namespace std;
int a,le,ri,ans,mid;
int S1[500005],A[500005];
vector < pair < int , int > > v;
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    le=0; ri=M; ans=-1;
    while(le<=ri) {
        mid=(le+ri)/2;
        for(int i=0;i<N;i++)
        S1[i]=S[i];
        for(int i=0;i<mid;i++) {
            swap(S1[X[i]],S1[Y[i]]);
        }
        for(int i=0;i<N;i++) {
            A[S1[i]]=i;
        }
        v.clear();
        for(int i=0;i<N;i++) {
            if(S1[i]==i) continue;
            v.push_back({i,S1[i]});
            swap(S1[i],S1[A[i]]);
            swap(A[i],A[S1[A[i]]]);   
        }
        a=v.size();
        if(a<=mid) {
            for(int i=0;i<N;i++) {
                S1[i]=S[i];
                A[S1[i]]=i;
            }
            for(int i=0;i<M;i++) {
                swap(A[S1[X[i]]],A[S1[Y[i]]]);
                swap(S1[X[i]],S1[Y[i]]);
                if(i<a) {
                    P[i]=A[v[i].first];
                    Q[i]=A[v[i].second];
                    swap(A[v[i].first],A[v[i].second]);
                    swap(S1[A[v[i].first]],S1[A[v[i].second]]);                    
                }
                else { P[i]=0; Q[i]=0; }
            }
            ri=mid-1;
            ans=mid;
        }
        else le=mid+1;
    }
    return ans;
}/*
int main() {
    findSwapPairs(5 , [4,3,2,1,0] , 6 , [0,1,2,3,0,1] , [1,2,3,4,1,2] , [] , [] );
}*/

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:26:17: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   26 |         a=v.size();
      |           ~~~~~~^~

Subtask #1
8.0 / 8.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
16.0 / 16.0

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

Subtask #4
18.0 / 18.0

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

Subtask #5
20.0 / 20.0

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

Subtask #6
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	492 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	2 ms	492 KB	Output is correct
4	Correct	2 ms	492 KB	Output is correct
5	Correct	2 ms	492 KB	Output is correct
6	Correct	2 ms	492 KB	Output is correct
7	Correct	2 ms	492 KB	Output is correct
8	Correct	2 ms	492 KB	Output is correct
9	Correct	2 ms	748 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	768 KB	Output is correct
12	Correct	2 ms	492 KB	Output is correct
13	Correct	3 ms	768 KB	Output is correct
14	Correct	2 ms	492 KB	Output is correct
15	Correct	220 ms	22228 KB	Output is correct
16	Correct	301 ms	22744 KB	Output is correct
17	Correct	310 ms	24020 KB	Output is correct
18	Correct	353 ms	20692 KB	Output is correct
19	Correct	277 ms	23124 KB	Output is correct
20	Correct	293 ms	24020 KB	Output is correct
21	Correct	256 ms	23892 KB	Output is correct
22	Correct	212 ms	19412 KB	Output is correct
23	Correct	257 ms	24916 KB	Output is correct
24	Correct	343 ms	24660 KB	Output is correct
25	Correct	380 ms	24348 KB	Output is correct
26	Correct	308 ms	23384 KB	Output is correct
27	Correct	302 ms	22640 KB	Output is correct
28	Correct	305 ms	24352 KB	Output is correct
29	Correct	347 ms	23892 KB	Output is correct
30	Correct	272 ms	21852 KB	Output is correct
31	Correct	379 ms	24404 KB	Output is correct
32	Correct	259 ms	24292 KB	Output is correct
33	Correct	363 ms	24532 KB	Output is correct
34	Correct	292 ms	24532 KB	Output is correct
35	Correct	280 ms	22864 KB	Output is correct
36	Correct	174 ms	20708 KB	Output is correct
37	Correct	356 ms	25172 KB	Output is correct
38	Correct	340 ms	24276 KB	Output is correct
39	Correct	348 ms	24532 KB	Output is correct

답안 #318033

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