# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
67942 |
2018-08-15T14:57:06 Z |
funcsr |
Sorting (IOI15_sorting) |
C++17 |
|
39 ms |
11000 KB |
#include "sorting.h"
#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define _1 first
#define _2 second
int S[100000];
bool used[100000];
vector<pair<int, int> > f(int R, int N, int SS[], int X[], int Y[]) {
rep(i, N) S[i] = SS[i];
rep(i, R) swap(S[X[i]], S[Y[i]]);
rep(i, N) used[i] = false;
vector<pair<int, int> > ret;
rep(s, N) if (!used[s]) {
vector<int> seq;
int v = s;
used[v] = true;
seq.pb(v);
while (true) {
v = S[v];
if (v == s) break;
assert(!used[v]);
seq.pb(v);
used[v] = true;
}
for (int i=seq.size()-1; i>0; i--) ret.pb(make_pair(seq[0], seq[i]));
}
if (ret.size() > R) return {};
return ret;
}
int rev[100000];
void swapV(int a, int b) {
swap(rev[S[a]], rev[S[b]]);
swap(S[a], S[b]);
}
int findSwapPairs(int N, int SS[], int M, int X[], int Y[], int P[], int Q[]) {
if (is_sorted(SS, SS+N)) return 0;
int lo = 0, hi = M;
while (hi-lo>1) {
int mid = (lo+hi)/2;
if (!f(mid, N, SS, X, Y).empty()) hi = mid;
else lo = mid;
}
int R = hi;
vector<pair<int,int> > swaps = f(R, N, SS, X, Y);
assert(swaps.size() <= R);
//cout<<"R="<<R<<": swaps={";for(auto p:swaps)cout<<p._1<<"<->"<<p._2<<",";cout<<"}\n";
rep(i, N) S[i] = SS[i], rev[SS[i]] = i;
rep(i, R) {
swapV(X[i], Y[i]);
if (i < swaps.size()) P[i] = rev[swaps[i]._1], Q[i] = rev[swaps[i]._2];
else P[i] = Q[i] = 0;
swapV(P[i], Q[i]);
}
return R;
}
Compilation message
sorting.cpp: In function 'std::vector<std::pair<int, int> > f(int, int, int*, int*, int*)':
sorting.cpp:31:26: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
for (int i=seq.size()-1; i>0; i--) ret.pb(make_pair(seq[0], seq[i]));
~~~~~~~~~~^~
sorting.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (ret.size() > R) return {};
~~~~~~~~~~~^~~
In file included from /usr/include/c++/7/cassert:44:0,
from sorting.cpp:5:
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:52:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
assert(swaps.size() <= R);
~~~~~~~~~~~~~^~~~
sorting.cpp:57:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (i < swaps.size()) P[i] = rev[swaps[i]._1], Q[i] = rev[swaps[i]._2];
~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
256 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
256 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
3 ms |
256 KB |
Output is correct |
10 |
Correct |
3 ms |
256 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
2 ms |
384 KB |
Output is correct |
4 |
Correct |
2 ms |
384 KB |
Output is correct |
5 |
Correct |
2 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
3 ms |
256 KB |
Output is correct |
4 |
Correct |
3 ms |
256 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
2 ms |
384 KB |
Output is correct |
7 |
Correct |
3 ms |
384 KB |
Output is correct |
8 |
Correct |
2 ms |
256 KB |
Output is correct |
9 |
Correct |
3 ms |
256 KB |
Output is correct |
10 |
Correct |
3 ms |
256 KB |
Output is correct |
11 |
Correct |
3 ms |
384 KB |
Output is correct |
12 |
Correct |
3 ms |
384 KB |
Output is correct |
13 |
Correct |
2 ms |
384 KB |
Output is correct |
14 |
Correct |
2 ms |
384 KB |
Output is correct |
15 |
Correct |
2 ms |
384 KB |
Output is correct |
16 |
Correct |
2 ms |
384 KB |
Output is correct |
17 |
Correct |
2 ms |
384 KB |
Output is correct |
18 |
Correct |
2 ms |
512 KB |
Output is correct |
19 |
Correct |
2 ms |
384 KB |
Output is correct |
20 |
Correct |
2 ms |
384 KB |
Output is correct |
21 |
Correct |
4 ms |
512 KB |
Output is correct |
22 |
Correct |
3 ms |
512 KB |
Output is correct |
23 |
Correct |
4 ms |
512 KB |
Output is correct |
24 |
Correct |
3 ms |
512 KB |
Output is correct |
25 |
Correct |
4 ms |
512 KB |
Output is correct |
26 |
Correct |
3 ms |
512 KB |
Output is correct |
27 |
Correct |
3 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
4 ms |
512 KB |
Output is correct |
11 |
Correct |
5 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
4 ms |
484 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
512 KB |
Output is correct |
2 |
Correct |
3 ms |
512 KB |
Output is correct |
3 |
Correct |
5 ms |
512 KB |
Output is correct |
4 |
Correct |
3 ms |
384 KB |
Output is correct |
5 |
Correct |
3 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
512 KB |
Output is correct |
7 |
Correct |
5 ms |
512 KB |
Output is correct |
8 |
Correct |
3 ms |
512 KB |
Output is correct |
9 |
Correct |
5 ms |
512 KB |
Output is correct |
10 |
Correct |
4 ms |
512 KB |
Output is correct |
11 |
Correct |
5 ms |
512 KB |
Output is correct |
12 |
Correct |
3 ms |
512 KB |
Output is correct |
13 |
Correct |
4 ms |
484 KB |
Output is correct |
14 |
Correct |
4 ms |
384 KB |
Output is correct |
15 |
Runtime error |
39 ms |
11000 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
16 |
Halted |
0 ms |
0 KB |
- |