| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 971022 |
2024-04-27T20:07:16 Z |
bigo |
Sorting (IOI15_sorting) |
C++14 |
|
32 ms |
624 KB |
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef pair<ll, ll> pii;
#define all(a) a.begin(),a.end()
#define rep(i,a,b) for(int i=a;i<b;i++)
const ll mod = 1e9 + 7;
const ll MAXN = 2e5 + 1;
vector<vector<int>>mag;
vector<int>we,vec,vec1;
vector<bool>visit;
int ans = 0;
void dfs(int v,int p) {
visit[v] = true;
we[v] = p;
mag[p].push_back(v);
if(!visit[vec[v]])
dfs(vec[v],p);
}
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
mag.resize(n);
we.resize(n);
visit.resize(n);
vec1.resize(n);
vec.resize(n);
rep(i, 0, n) vec[i] = S[i];
rep(i, 0, n) {
vec1[vec[i]] = i;
}
int cnt = 0;
rep(i, 0, n) {
if (!visit[i]) {
dfs(i, cnt);
cnt++;
}
}
ans = 0;
rep(i, 0, n)
ans += max((int)mag[i].size() - 1, 0);
if (ans == 0)
return 0;
rep(R, 1, m+1) {
swap(vec[X[R - 1]], vec[Y[R - 1]]);
swap(vec1[vec[X[R - 1]]], vec1[vec[Y[R - 1]]]);
mag.clear();
we.clear();
visit.clear();
mag.resize(n);
we.resize(n);
visit.resize(n);
int cnt = 0;
rep(i, 0, n) {
if (!visit[i]) {
dfs(i, cnt);
cnt++;
}
}
ans = 0;
rep(i, 0, n)
ans += max((int)mag[i].size() - 1, 0);
if (ans <= R) {
int sz = 0;
rep(i, 0, n) {
rep(j, 0, (int)mag[i].size() - 1) {
P[sz] = vec1[mag[i][j]];
Q[sz] = vec1[mag[i][j+1]];
sz++;
}
}
return R;
}
}
}
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:61:7: warning: declaration of 'cnt' shadows a previous local [-Wshadow]
61 | int cnt = 0;
| ^~~
sorting.cpp:40:6: note: shadowed declaration is here
40 | int cnt = 0;
| ^~~
sorting.cpp:83:1: warning: control reaches end of non-void function [-Wreturn-type]
83 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
32 ms |
624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
