# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
314808 | 2020-10-21T10:52:18 Z | amunduzbaev | 정렬하기 (IOI15_sorting) | C++14 | 2 ms | 512 KB |
//#include "grader.cpp" #include "sorting.h" #include <bits/stdc++.h> using namespace std; #define pb(a) push_back(a) const int N=2*1e5+5; int n,s[N], x[N], y[N] ,pos[N], used[N]; vector<pair<int,int >> check(int m){ vector<int> tmp(n); for(int i=0;i<n;i++) tmp[i]=s[i]; for(int i=0;i<n;i++) swap(tmp[x[i]],tmp[y[i]]); for(int i=0;i<n;i++) pos[tmp[i]]=i; vector<pair<int,int>>swaps; for(int i=0;i<n;i++){ if(tmp[i]==i) continue; swaps.push_back({i,pos[i]}); pos[tmp[i]]=pos[i]; swap(tmp[i],tmp[pos[i]]); } vector<pair<int,int>> ans; int i; for(i=0;i<swaps.size();i++){ int a=swaps[i].first, b=swaps[i].second; ans.push_back({a,b}); swap(tmp[x[i]],tmp[y[i]]); swap(pos[tmp[x[i]]], pos[tmp[y[i]]]); swap(tmp[a],tmp[b]); swap(pos[tmp[a]], pos[tmp[b]]); } for(; i<m;i++){ ans.push_back({0, 0}); } return ans; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int p[], int q[]) { n=N; for(int i=0;i<n;i++) s[i]=S[i]; for(int i=0;i<M;i++) x[i]=X[i], y[i]= Y[i]; int l=0,r=M; while(l<r) { int mid=(l+r)/2; if(check(mid).size() <= M) r=mid; else l=mid+1; } vector<pair<int,int>>ans = check(l); for(int i=0;i<ans.size();i++){ p[i]=ans[i].first, q[i]=ans[i].second; } return ans.size(); }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 512 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 KB | Output is correct |
2 | Correct | 0 ms | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 512 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 384 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 | 384 KB | Output is correct |
3 | Correct | 1 ms | 384 KB | Output is correct |
4 | Correct | 0 ms | 384 KB | Output is correct |
5 | Correct | 1 ms | 512 KB | Output is correct |
6 | Correct | 1 ms | 384 KB | Output is correct |
7 | Correct | 1 ms | 384 KB | Output is correct |
8 | Correct | 1 ms | 384 KB | Output is correct |
9 | Correct | 1 ms | 384 KB | Output is correct |
10 | Correct | 1 ms | 384 KB | Output is correct |
11 | Correct | 1 ms | 384 KB | Output is correct |
12 | Correct | 1 ms | 384 KB | Output is correct |
13 | Correct | 1 ms | 384 KB | Output is correct |
14 | Incorrect | 1 ms | 384 KB | Output isn't correct |
15 | 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 | - |