# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
580007 | 2022-06-20T13:15:57 Z | AugustinasJucas | 정렬하기 (IOI15_sorting) | C++14 | 255 ms | 14632 KB |
#include "sorting.h" #include <bits/stdc++.h> using namespace std; int n; int m; vector<int> mas; vector<pair<int, int> > swaps; vector<int> simuliuok(int kiek) { vector<int> ret(n); for(int i = 0; i < n; i++) ret[i] = i; for(int i = 0; i < kiek; i++) { swap(ret[swaps[i].first], ret[swaps[i].second]); } return ret; } vector<int> iKuriaLekstutePerkelti(int kiek){ vector<int> kuriLekstuteCiaAtsidurs = simuliuok(kiek); // cout << "simluliantas: "; for(auto &x : kuriLekstuteCiaAtsidurs) cout << x << " "; // cout << endl; vector<int> kurEisiu (n); for(int i = 0; i < n; i++) { kurEisiu[i] = kuriLekstuteCiaAtsidurs[mas[i]]; } return kurEisiu; } bool f(int kiek) { vector<int> kurEisiu = iKuriaLekstutePerkelti(kiek); vector<bool> vis(n, false); int s = 0; for(int i = 0; i < n; i++) { if(vis[i]) continue; for(int j = kurEisiu[i]; j != i; j = kurEisiu[j]) { vis[j] = true; s++; } vis[i] = true; } return s <= kiek; } vector<pair<int, int> > raskEiliskuma(vector<int> kurEisiu) { vector<bool> vis(n, false); vector<pair<int, int> > ret; for(int i = 0; i < n; i++) { if(vis[i]) continue; vis[i] = true; vector<int> ratas = {i}; for(int j = kurEisiu[i]; j != i; j = kurEisiu[j]) { ratas.push_back(j); vis[j] = true; } // cout << "ratas: "; for(auto &x : ratas) cout << x << " "; // cout << endl; for(int i = ratas.size() - 1; i > 0; i--) { ret.push_back({ratas[i], ratas[i-1]}); } } return ret; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N; m = M; for(int i = 0; i < n; i++) { mas.push_back(S[i]); } for(int i = 0; i < m; i++) { swaps.push_back({X[i], Y[i]}); } int ans; int l = 0; int r = m; int mid; while(l <= r) { mid = (l + r) / 2; if(f(mid)) { ans = mid; r = mid-1; }else { l = mid+1; } } vector<int> kurEisiu = iKuriaLekstutePerkelti(ans); vector<pair<int, int> > eiliskumas = raskEiliskuma(kurEisiu); // cout << "kurEisiu: "; for(auto &x : kurEisiu) cout << x << " "; // cout << endl << "eiliskumas: " << endl; // for(auto &x : eiliskumas) { // cout << "swp " << x.first << " lekstutes turini su " << x.second << " lekstutes turiniu" << endl; // } vector<int> lekstute(n), kurLekstute(n); for(int i = 0; i < n; i++) lekstute[i] = i, kurLekstute[i] = i; //cout << endl; for(int i = 0; i < ans; i++) { kurLekstute[lekstute[X[i]]] = Y[i]; kurLekstute[lekstute[Y[i]]] = X[i]; swap(lekstute[X[i]], lekstute[Y[i]]); int A, B; if(i >= eiliskumas.size()) A = B = 0; else { A = eiliskumas[i].first; B = eiliskumas[i].second; } P[i] = kurLekstute[A]; Q[i] = kurLekstute[B]; //cout << "swap " << X[i] << " su " << Y[i] << ". Tada lekstutes issidesciusios taip:"; for(auto x : lekstute) cout << x << " "; cout << endl; //cout << "tada swapinsiu lekstutes " << A << " turini su lekstutes " << B << " turiniu " << endl; //cout << "T.y., swap " << P[i] << " su " << Q[i] << endl << endl; } return ans; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 212 KB | Expected EOLN |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 212 KB | Expected EOLN |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Incorrect | 1 ms | 212 KB | Expected EOLN |
3 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Incorrect | 1 ms | 212 KB | Expected EOLN |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 255 ms | 14632 KB | Expected EOLN |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 255 ms | 14632 KB | Expected EOLN |
2 | Halted | 0 ms | 0 KB | - |