# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
133627 | 2019-07-21T07:01:17 Z | ckodser | 정렬하기 (IOI15_sorting) | C++14 | 663 ms | 524292 KB |
#include "sorting.h" #include<bits/stdc++.h> #define ll int #define pb push_back #define ld long double #define mp make_pair #define F first #define S second #define pii pair<ll,ll> using namespace :: std; const ll maxn=2e5+500; const ll inf=1e9+900; ll per[maxn]; ll s[maxn]; ll x[maxn]; ll y[maxn]; ll n,m; vector<pii> vec; void dfs(ll a){ if(per[a]==a)return; vec.pb(mp(a,per[a])); swap(per[a],per[per[a]]); dfs(a); } void copytoper(){ for(ll i=0;i<n;i++){ per[i]=s[i]; } } bool mishe(ll mid){ copytoper(); for(ll i=0;i<mid;i++){ swap(per[x[i]],per[y[i]]); } vec.clear(); for(ll i=0;i<n;i++){ dfs(i); } return (vec.size()<=mid); } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n=N,m=M; for(ll i=0;i<n;i++){ s[i]=S[i]; } for(ll i=0;i<m;i++){ x[i]=X[i]; y[i]=Y[i]; } ll b=-1; ll e=M; while(e-b>1){ ll mid=(e+b)/2; if(mishe(mid)){ e=mid; }else{ b=mid; } } // ans=e; copytoper(); for(ll i=0;i<e;i++){ swap(per[x[i]],per[y[i]]); } vec.clear(); for(ll i=0;i<n;i++){ dfs(i); } while(vec.size()<e){ vec.pb(mp(0,0)); } if(vec.size()>e){ exit(1); cout<<"WTF?!"; return 0; } for(ll i=0;i<n;i++){ per[i]=i; } for(ll i=e-1;i>=0;i--){ swap(per[x[i]],per[y[i]]); } vector<pii> ans; for(ll i=0;i<e;i++){ swap(per[x[i]],per[y[i]]); pii a=vec[i]; ll b1,b2; for(ll i=0;i<n;i++){ if(per[i]==a.F)b1=i; if(per[i]==a.S)b2=i; } ans.pb(mp(b1,b2)); } for(ll i=0;i<e;i++){ P[i]=ans[i].F; Q[i]=ans[i].S; } copytoper(); for(ll i=0;i<e;i++){ // cout<<P[i]<<' '<<Q[i]<<endl; swap(per[x[i]],per[y[i]]); swap(per[Q[i]],per[P[i]]); } for(ll i=0;i<n;i++){ if(per[i]!=i){ while(per[i]!=i){ per[i+1]=i; } } } return e; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | 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 | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 352 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 | 424 KB | Output is correct |
5 | Correct | 2 ms | 376 KB | Output is correct |
6 | Correct | 2 ms | 376 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | 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 | 376 KB | Output is correct |
7 | Correct | 2 ms | 376 KB | Output is correct |
8 | Correct | 2 ms | 376 KB | Output is correct |
9 | Correct | 2 ms | 376 KB | Output is correct |
10 | Correct | 2 ms | 376 KB | Output is correct |
11 | Correct | 2 ms | 504 KB | Output is correct |
12 | Correct | 2 ms | 376 KB | Output is correct |
13 | Correct | 2 ms | 352 KB | Output is correct |
14 | Correct | 2 ms | 376 KB | Output is correct |
15 | Correct | 2 ms | 376 KB | Output is correct |
16 | Correct | 2 ms | 424 KB | Output is correct |
17 | Correct | 2 ms | 376 KB | Output is correct |
18 | Correct | 2 ms | 376 KB | Output is correct |
19 | Correct | 2 ms | 376 KB | Output is correct |
20 | Correct | 2 ms | 348 KB | Output is correct |
21 | Correct | 3 ms | 760 KB | Output is correct |
22 | Correct | 3 ms | 632 KB | Output is correct |
23 | Correct | 3 ms | 760 KB | Output is correct |
24 | Correct | 3 ms | 660 KB | Output is correct |
25 | Correct | 3 ms | 680 KB | Output is correct |
26 | Correct | 3 ms | 808 KB | Output is correct |
27 | Correct | 3 ms | 760 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 632 KB | Output is correct |
2 | Correct | 7 ms | 632 KB | Output is correct |
3 | Correct | 7 ms | 632 KB | Output is correct |
4 | Correct | 3 ms | 632 KB | Output is correct |
5 | Correct | 3 ms | 632 KB | Output is correct |
6 | Correct | 4 ms | 632 KB | Output is correct |
7 | Correct | 6 ms | 632 KB | Output is correct |
8 | Correct | 7 ms | 632 KB | Output is correct |
9 | Correct | 7 ms | 632 KB | Output is correct |
10 | Correct | 7 ms | 732 KB | Output is correct |
11 | Correct | 7 ms | 632 KB | Output is correct |
12 | Correct | 5 ms | 632 KB | Output is correct |
13 | Correct | 7 ms | 632 KB | Output is correct |
14 | Correct | 2 ms | 504 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 6 ms | 632 KB | Output is correct |
2 | Correct | 7 ms | 632 KB | Output is correct |
3 | Correct | 7 ms | 632 KB | Output is correct |
4 | Correct | 3 ms | 632 KB | Output is correct |
5 | Correct | 3 ms | 632 KB | Output is correct |
6 | Correct | 4 ms | 632 KB | Output is correct |
7 | Correct | 6 ms | 632 KB | Output is correct |
8 | Correct | 7 ms | 632 KB | Output is correct |
9 | Correct | 7 ms | 632 KB | Output is correct |
10 | Correct | 7 ms | 732 KB | Output is correct |
11 | Correct | 7 ms | 632 KB | Output is correct |
12 | Correct | 5 ms | 632 KB | Output is correct |
13 | Correct | 7 ms | 632 KB | Output is correct |
14 | Correct | 2 ms | 504 KB | Output is correct |
15 | Runtime error | 663 ms | 524292 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
16 | Halted | 0 ms | 0 KB | - |