# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
316640 | 2020-10-27T00:19:55 Z | jainbot27 | 정렬하기 (IOI15_sorting) | C++17 | 2 ms | 512 KB |
/* Observation: if we can do it in N turns, we can do it in N + 1 */ #include <bits/stdc++.h> using namespace std; #define f first #define s second #define pb push_back #define ar array #define all(x) x.begin(), x.end() #define siz(x) (int)x.size() #define FOR(x, y, z) for(int x = (y); x < (z); x++) #define ROF(x, z, y) for(int x = (y-1); x >= (z); x--) #define F0R(x, z) FOR(x, 0, z) #define R0F(x, z) ROF(x, 0, z) #define trav(x, y) for(auto&x:y) using ll = long long; using vi = vector<int>; using vl = vector<long long>; using pii = pair<int, int>; using vpii = vector<pair<int, int>>; template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;} template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;} mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const char nl = '\n'; const int mxN = 2e5 + 10; const int MOD = 1e9 + 7; const long long infLL = 1e18; int findSwapPairs(int n, int* s, int M, int* x, int *y, int *p, int *q){ int l = -1, r = M; vpii ans; while(l < r){ int m = l + r; m = (m - (m&1)) / 2; vi pos(n); vi cur(n); vpii ops; F0R(i, n){ cur[i] = s[i]; } F0R(i, m + 1){ swap(cur[x[i]], cur[y[i]]); } F0R(i, n){ pos[cur[i]] = i; } F0R(i, n){ if(cur[i] != i){ int x = cur[i]; // whats currently at the spot we want int z = pos[i]; // the pos of our current element ops.pb({i, pos[i]}); cur[z] = x; cur[i] = i; pos[i] = i; pos[x] = z; } } if(siz(ops) - 1 <= m){ ans = ops; r = m; } else{ l = m + 1; } } F0R(i, l + 1){ if(i < ans.size()){ x[i] = ans[i].f; y[i] = ans[i].s; } else{ x[i] = 0; y[i] = 0; } } return l + 1; } //int32_t main(){ // ios_base::sync_with_stdio(0); cin.tie(0); // int N; // cin >> N; // int S[N]; // F0R(i, N){ // cin >> S[i]; // } // int M; // cin >> M; // int X[M], Y[M]; // F0R(i, M){ // cin >> X[i] >> Y[i]; // } // int P[M], Q[M]; // int res = findSwapPairs(N, S, M, X, Y, P, Q); // cout << res << nl; // return 0; //}
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Incorrect | 1 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Incorrect | 1 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 256 KB | Output is correct |
2 | Incorrect | 1 ms | 384 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 256 KB | Output is correct |
3 | Incorrect | 1 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 2 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |