# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
170904 |
2019-12-26T16:46:56 Z |
socho |
Sorting (IOI15_sorting) |
C++14 |
|
3 ms |
504 KB |
#include "sorting.h"
#include "bits/stdc++.h"
using namespace std;
const int MXN = 200005;
int n, m;
int seq[MXN];
pair<int, int> plan[MXN];
vector<pair<int, int> > ans;
bool works(int sw) {
// cout << "try: " << sw << ' ';
ans.clear();
int nsw[n];
for (int i=0; i<n; i++) nsw[i] = seq[i];
int where[n];
for (int i=0; i<sw; i++) {
int a = plan[i].first, b = plan[i].second;
swap(nsw[a], nsw[b]);
}
for (int i=0; i<n; i++) {
where[nsw[i]] = i;
}
int need = 0;
for (int i=0; i<n; i++) {
if (nsw[i] == i) continue;
need++;
int ati = nsw[i];
int whei = where[i];
where[ati] = whei;
where[i] = i;
nsw[i] = i;
nsw[whei] = ati;
ans.push_back(make_pair(i, whei));
}
// cout << (need <= sw) << endl;
// if (sw == 3) return true;
return need <= sw;
}
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++) seq[i] = S[i];
for (int i=0; i<m; i++) {
plan[i].first = X[i];
plan[i].second = Y[i];
}
int low = 0;
int high = M + 1;
while (low + 1 < high) {
int mid = (low + high) / 2;
if (works(mid)) {
high = mid;
}
else {
low = mid;
}
}
if (works(low)) {
works(low);
for (int i=0; i<low; i++) {
P[i] = ans[i].first;
Q[i] = ans[i].second;
}
return low;
}
else {
works(high);
for (int i=0; i<high; i++) {
P[i] = ans[i].first;
Q[i] = ans[i].second;
}
return high;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
284 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
284 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
308 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
408 KB |
Output is correct |
10 |
Correct |
2 ms |
372 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
284 KB |
Output is correct |
2 |
Correct |
2 ms |
256 KB |
Output is correct |
3 |
Correct |
2 ms |
376 KB |
Output is correct |
4 |
Correct |
2 ms |
256 KB |
Output is correct |
5 |
Correct |
2 ms |
256 KB |
Output is correct |
6 |
Correct |
2 ms |
256 KB |
Output is correct |
7 |
Correct |
2 ms |
308 KB |
Output is correct |
8 |
Correct |
2 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
408 KB |
Output is correct |
10 |
Correct |
2 ms |
372 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
2 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
504 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |