# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
314578 | 2020-10-20T11:16:37 Z | talant117408 | Sorting (IOI15_sorting) | C++17 | 97 ms | 504 KB |
#include "sorting.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair <ll, ll> pii; #define precision(n) fixed << setprecision(n) #define pb push_back #define ub upper_bound #define lb lower_bound #define mp make_pair #define eps (double)1e-9 #define PI 2*acos(0.0) #define endl "\n" #define sz(v) int((v).size()) #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() #define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); inline bool isvowel(char ch){ ch = tolower(ch); return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u'); } inline bool isprime(int n){ if(n < 2 || (n%2 == 0 && n != 2)) return false; for(int i = 3; i*i <= n; i++) if(n%i == 0) return false; return true; } const int NN = 6e5+7; int pos[NN]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { int i, j; for(i = 0; i < N; i++){ pos[S[i]] = i; } for(i = 0; i < M; i++){ swap(pos[S[X[i]]], pos[S[Y[i]]]); swap(S[X[i]], S[Y[i]]); int tmp = 0, tmpS[N], tmpos[N]; vector <pii> res; vector <int> vis(N), cyc; for(j = 0; j < N; j++){ tmpS[j] = S[j]; tmpos[j] = pos[j]; } for(j = 0; j < N; j++){ if(vis[j]) continue; int k = j; while(!vis[k]){ vis[k] = 1; cyc.pb(tmpS[k]); k = tmpS[k]; } tmp += sz(cyc)-1; for(k = 0; k < sz(cyc)-1; k++){ res.pb(mp(tmpos[cyc[k]], tmpos[cyc[k+1]])); swap(tmpos[cyc[k]], tmpos[cyc[k+1]]); swap(tmpS[tmpos[cyc[k]]], tmpS[tmpos[cyc[k+1]]]); swap(cyc[k], cyc[k+1]); } cyc.clear(); } if(tmp <= i+1){ while(sz(res) <= i){ res.pb(mp(0, 0)); } for(j = 0; j < sz(res); j++){ P[j] = res[j].first; Q[j] = res[j].second; } return sz(res); } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 288 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 384 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 97 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 97 ms | 504 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |