# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
485850 | 2021-11-09T14:24:21 Z | MilosMilutinovic | Sorting (IOI15_sorting) | C++14 | 1 ms | 460 KB |
#include <bits/stdc++.h> using namespace std; #define rep(i,a,n) for (int i=a;i<n;i++) #define per(i,a,n) for (int i=n-1;i>=a;i--) #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define fi first #define se second #define SZ(x) ((int)(x).size()) typedef vector<int> VI; typedef long long ll; typedef pair<int,int> PII; typedef double db; mt19937 mrand(random_device{}()); const ll mod=1000000007; const ll mod2=998244353; int rnd(int x) { return mrand() % x;} ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;} // head const int N=201000; int n,a[N],s[N],id[N],pos[N],x[N],y[N]; bool check(int r) { rep(i,0,n) a[i]=s[i],id[i]=i; rep(i,0,r) { swap(a[x[i]],a[y[i]]); } rep(i,0,n) pos[a[i]]=i; int cnt=0; rep(i,0,n) { if (pos[i]==i) continue; int w=a[i]; swap(a[pos[i]],a[i]); swap(pos[i],pos[w]); cnt++; } return cnt<=r; } void gao(int r,int* p,int* q) { rep(i,0,n) a[i]=s[i],id[i]=i; rep(i,0,r) { swap(a[x[i]],a[y[i]]); } rep(i,0,n) pos[a[i]]=i; int cnt=0; vector<PII> todo; rep(i,0,n) { if (pos[i]==i) continue; todo.pb(mp(i,a[i])); int w=a[i]; swap(a[pos[i]],a[i]); swap(pos[i],pos[w]); } assert(is_sorted(a,a+n)); rep(i,0,n) a[i]=s[i],pos[a[i]]=i; rep(i,0,r) { swap(a[x[i]],a[y[i]]); if (i<SZ(todo)) { p[i]=pos[todo[i].fi]; q[i]=pos[todo[i].se]; swap(a[p[i]],a[q[i]]); swap(pos[todo[i].fi],pos[todo[i].se]); } else p[i]=q[i]=0; } //rep(i,0,n) printf("%d ",a[i]); puts(""); //assert(is_sorted(a,a+n)); rep(i,SZ(todo),r) p[i]=q[i]=0; } int findSwapPairs(int n,int* s,int m,int* x,int* y,int* p,int* q) { if (is_sorted(s,s+n)) return 0; ::n=n; rep(i,0,n) ::s[i]=s[i]; rep(i,0,m) ::x[i]=x[i],::y[i]=y[i]; int l=1,r=n,ans=1; while (l<=r) { int md=l+r>>1; if (check(md)) ans=md,r=md-1; else l=md+1; } gao(ans,p,q); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 0 ms | 216 KB | Output is correct |
7 | Correct | 0 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 0 ms | 216 KB | Output is correct |
7 | Correct | 0 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 0 ms | 332 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Incorrect | 0 ms | 332 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | Output is correct |
2 | Correct | 0 ms | 204 KB | Output is correct |
3 | Correct | 0 ms | 332 KB | Output is correct |
4 | Correct | 0 ms | 332 KB | Output is correct |
5 | Correct | 0 ms | 332 KB | Output is correct |
6 | Correct | 0 ms | 216 KB | Output is correct |
7 | Correct | 0 ms | 332 KB | Output is correct |
8 | Correct | 1 ms | 204 KB | Output is correct |
9 | Correct | 0 ms | 204 KB | Output is correct |
10 | Correct | 1 ms | 332 KB | Output is correct |
11 | Correct | 0 ms | 332 KB | Output is correct |
12 | Correct | 0 ms | 332 KB | Output is correct |
13 | Correct | 0 ms | 204 KB | Output is correct |
14 | Incorrect | 0 ms | 332 KB | Output isn't correct |
15 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 460 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 460 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |