제출 #115038

#제출 시각아이디문제언어결과실행 시간메모리
115038MladenP정렬하기 (IOI15_sorting)C++17
74 / 100
43 ms14840 KiB
#include<bits/stdc++.h> #define STIZE(x) fprintf(stderr, "STIZE%d\n", x); #define PRINT(x) fprintf(stderr, "%s = %d\n", #x, x); #define NL(x) printf("%c", " \n"[(x)]); #define lld long long #define pii pair<int,int> #define pb push_back #define fi first #define se second #define mid (l+r)/2 #define endl '\n' #define all(a) begin(a),end(a) #define sz(a) int((a).size()) #define LINF 1000000000000000LL #define INF 1000000000 #define EPS 1e-9 using namespace std; #define MAXN 200010 int n, s[MAXN], m, x[MAXN], y[MAXN], p[MAXN], q[MAXN], idxx, idx[MAXN]; bool pos[MAXN]; void DFS(int node) { pos[node] = 1; if(!pos[s[node]]) DFS(s[node]); } void DFS1(int node) { pos[node] = 1; if(!pos[s[node]]) { p[idxx] = node; q[idxx] = s[node]; idxx++; DFS1(s[node]); } } bool check(int key) { for(int i = 0; i < key; i++) swap(s[x[i]], s[y[i]]); for(int i = 0; i < n; i++) pos[i] = 0; int cnt = 0; for(int i = 0; i < n; i++) { if(!pos[i]) DFS(i), cnt++; } return n-cnt <= key; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { n = N, m = M; int rez = M, l = 1, r = M; bool sorted = 1; for(int i = 0; i < N; i++) if(S[i] != i) sorted = 0; for(int i = 0; i < M; i++) x[i] = X[i], y[i] = Y[i]; if(sorted) return 0; for(int i = 0; i < N; i++) s[i] = S[i], idx[s[i]] = i; while(l <= r) { if(check(mid)) rez = mid, r = mid-1; else l = mid+1; for(int i = 0; i < n; i++) s[i] = S[i]; } for(int i = 0; i < rez; i++) swap(s[X[i]], s[Y[i]]); for(int j = 0; j < N; j++) pos[j] = 0; for(int j = 0; j < N; j++) { if(!pos[j]) DFS1(j); } for(int j = 0; j < idxx; j++) P[j] = p[j], Q[j] = q[j]; for(int j = idxx; j < rez; j++) P[j] = 0, Q[j] = 0; for(int i = 0; i < rez; i++) { swap(S[X[i]], S[Y[i]]); swap(idx[S[X[i]]], idx[S[Y[i]]]); P[i] = idx[s[P[i]]], Q[i] = idx[s[Q[i]]]; swap(S[P[i]], S[Q[i]]); swap(idx[S[P[i]]], idx[S[Q[i]]]); } return rez; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...