Submission #115021

#TimeUsernameProblemLanguageResultExecution timeMemory
115021MladenPSorting (IOI15_sorting)C++17
0 / 100
166 ms696 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], idx; 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[idx] = node; q[idx] = s[node]; idx++; DFS1(s[node]); } } 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++) s[i] = S[i]; for(int i = 0; i < M; i++) x[i] = X[i], y[i] = Y[i]; for(int i = 0; i < M; i++) { swap(s[x[i]], s[y[i]]); fill(pos, pos+MAXN, 0); int cnt = 0; for(int j = 0; j < N; j++) { if(!pos[j]) DFS(j), cnt++; } if(n-cnt <= i) { fill(pos, pos+MAXN, 0); for(int j = 0; j < N; j++) { if(!pos[j]) DFS1(j); } for(int j = 0; j < idx; j++) P[j] = p[j], Q[j] = q[j]; for(int j = idx; j < i; j++) P[j] = 0, Q[j] = 0; return i+1; } } } /* int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cerr.tie(0); cin >> n; for(int i = 0; i < n; i++) cin >> s[i]; cin >> m; for(int i = 0; i < m; i++) cin >> x[i] >> y[i]; int r = findSwapPairs(n, s, m, x, y, p, q); cout << r << endl; for(int i = 0; i < r; i++) cout << p[i] << ' ' << q[i] << endl; } */

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...