# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
307485 | 2020-09-28T10:25:24 Z | lohacho | 정렬하기 (IOI15_sorting) | C++14 | 2 ms | 512 KB |
#include "sorting.h" #include <bits/stdc++.h> using namespace std; using LL = long long; const int INF = (int)1e9 + 7; const int NS = (int)2e5 + 4; int mov[NS], Index[NS], pos[NS], S_save[NS], ba[NS]; int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { for(int i = 0; i < N; ++i){ S_save[i] = S[i]; } int low = 0, high = N - 1, mid; function < int() > can_sort = [&](){ for(int i = 0; i < N; ++i){ S[i] = S_save[i]; mov[i] = i; Index[S[i]] = i; ba[i] = S[i]; pos[S[i]] = i; } for(int i = mid - 1; i >= 0; --i){ swap(mov[X[i]], mov[Y[i]]); } int diff = 0; for(int i = 0; i < mid; ++i){ while(diff < N && mov[diff] == S[diff]) ++diff; swap(Index[ba[X[i]]], Index[ba[Y[i]]]); swap(ba[X[i]], ba[Y[i]]); if(diff >= N){ P[i] = Q[i] = 0; } else{ P[i] = Index[S[diff]], Q[i] = Index[mov[diff]]; swap(Index[S[diff]], Index[mov[diff]]); swap(ba[P[i]], ba[Q[i]]); swap(S[diff], S[pos[mov[diff]]]); } } while(diff < N && mov[diff] == S[diff]) ++diff; if(diff >= N) return 1; else return 0; }; while(low < high){ mid = (low + high) >> 1; for(int i = 0; i < N; ++i) P[i] = Q[i] = 0; if(can_sort()){ high = mid; } else{ low = mid + 1; } } return low; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Incorrect | 0 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 | 384 KB | Output is correct |
3 | Incorrect | 0 ms | 384 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 384 KB | Output is correct |
2 | Incorrect | 0 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 | 384 KB | Output is correct |
3 | Incorrect | 0 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 | - |