# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
314601 | 2020-10-20T12:38:46 Z | amunduzbaev | Sorting (IOI15_sorting) | C++14 | 2 ms | 544 KB |
//#include "grader.cpp" #include "sorting.h" #include <bits/stdc++.h> using namespace std; const int N=2*1e5+5; int n, s[N], x[N], y[N]; vector<pair<int,int>>ans; bool check(int m){ int a[N], pos[N]; for(int i=0;i<n;i++) a[i]=s[i]; for(int i=0;i<m;i++) swap(a[x[i]], a[y[i]]); for(int i=0;i<n;i++) pos[a[i]]=i; vector<pair<int,int > > swaps; for(int i=0;i<n;i++){ if(pos[i]!=i){ int j=pos[i]; swaps.push_back({a[i],a[j]}); pos[a[i]]=j; swap(a[i],a[j]); } } if(swaps.size()>m) return false; ans.clear(); /* cout<<m<<"\n"; for(int i=0;i<swaps.size();i++){ cout<<swaps[i].first<<" "<<swaps[i].second<<"\n"; } */ ans.assign(m, {0,0}); for(int i=0;i<n;i++) a[i]=s[i], pos[a[i]]=i; for(int i=0;i<swaps.size();i++){ int x1=x[i], y1=y[i], i1=swaps[i].first, j1=swaps[i].second; ans[i] = {pos[i1],pos[j1]}; i1=pos[i1],j1=pos[j1]; swap ( a[x1] ,a[y1] ); swap ( a[i1], a[j1] ); swap ( pos[a[x1]], pos[a[y1]] ); swap ( pos[a[i1]], pos[a[j1]] ); } return true; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n=N; for(int i=0;i<n;i++) s[i]=S[i]; for(int i=0;i<M;i++) x[i]=X[i], y[i]=Y[i]; int l=0,r=M; while(l<r){ int md=l+((r-l)/2); if(check(md)) r=md; else l=md+1; } for(int i=0;i<ans.size();i++){ P[i]=ans[i].first; Q[i]=ans[i].second; } return l; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Incorrect | 1 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 384 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 0 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Incorrect | 1 ms | 384 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 544 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 544 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |