| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 532818 |
2022-03-04T02:42:18 Z |
ivan24 |
Sorting (IOI15_sorting) |
C++14 |
|
3 ms |
844 KB |
#include "sorting.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
ll min (ll x, ll y){
return ((x < y) ? x : y);
}
ll max (ll x, ll y){
return ((x > y) ? x : y);
}
const ll INF = 1e18;
int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
p[0] = 0; q[0] = 1;
bool perfect = true;
for (ll i = 0; n > i; i++){
if (s[i] != i) perfect = false;
}
if (perfect) return 0;
ll lo = 1,hi = m,md;
md = (lo+hi/2);
while (hi >= lo){
md = (lo+hi)/2;
//cout << "md: " << md << endl;
vi v,v_idx;
v.resize(n);
v_idx.resize(n);
for (ll i = 0; n > i; i++){
v[i] = s[i]; v_idx[v[i]] = i;
}
for (ll i = 0; md > i; i++){
swap(v[x[i]],v[y[i]]);
swap(v_idx[v[x[i]]],v_idx[v[y[i]]]);
}
vi cur,cur_idx;
cur.resize(n);
cur_idx.resize(n);
vii swaps;
swaps.assign(md,ii(0,0));
for (ll i = 0; n > i; i++){
cur[i] = i; cur_idx[i] = i;
}
/*
cout << "v: ";
for (auto i: v) cout << i << " ";
cout << endl;
cout << "v_idx: ";
for (auto i: v_idx) cout << i << " ";
cout << endl;
cout << "cur: ";
for (auto i: cur) cout << i << " ";
cout << endl;
cout << "cur_idx: ";
for (auto i: cur_idx) cout << i << " ";
cout << endl;
*/
ll ptr = 0;
for (ll i = md-1; i >= 0; i--){
if (ptr >= n) continue;
while (n > ptr && cur_idx[ptr] == v_idx[ptr]) ptr++;
swaps.emplace_back(cur_idx[ptr],cur_idx[v[cur_idx[ptr]]]);
swap(cur[cur_idx[ptr]],cur[cur_idx[v[cur_idx[ptr]]]]);
swap(cur_idx[ptr],cur_idx[v[cur_idx[ptr]]]);
/*
cout << "swapped: " << cur_idx[ptr] << " and " << cur_idx[v[cur_idx[ptr]]] << " ptr: " << ptr << endl;
cout << "cur: ";
for (auto i: cur) cout << i << " ";
cout << endl;
cout << "cur_idx: ";
for (auto i: cur_idx) cout << i << " ";
cout << endl;
*/
swap(v_idx[v[x[i]]], v_idx[v[y[i]]]);
swap(v[x[i]],v[y[i]]);
swap(cur_idx[cur[x[i]]],cur_idx[cur[y[i]]]);
swap(cur[x[i]],cur[y[i]]);
}
bool works = true;
for (ll i = 0; n > i; i++) works = works && (cur[i] == v[i]);
/*
cout << "after: \n";
cout << "v: ";
for (auto i: v) cout << i << " ";
cout << endl;
cout << "v_idx: ";
for (auto i: v_idx) cout << i << " ";
cout << endl;
cout << "cur: ";
for (auto i: cur) cout << i << " ";
cout << endl;
cout << "cur_idx: ";
for (auto i: cur_idx) cout << i << " ";
cout << endl;
*/
if (works){
hi = md;
reverse(swaps.begin(),swaps.end());
for (ll i = 0; md > i; i++){
p[i] = swaps[i].F;
q[i] = swaps[i].S;
}
}else
lo = md+1;
if (hi == lo && hi == md) return md;
}
return md;
}
Compilation message
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:11:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
11 | #define F first
sorting.cpp:112:33: note: in expansion of macro 'F'
112 | p[i] = swaps[i].F;
| ^
sorting.cpp:12:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
12 | #define S second
sorting.cpp:113:33: note: in expansion of macro 'S'
113 | q[i] = swaps[i].S;
| ^
sorting.cpp:117:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
117 | if (hi == lo && hi == md) return md;
| ^~
sorting.cpp:119:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
119 | return md;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
248 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
248 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 6 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
248 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
204 KB |
Output is correct |
| 6 |
Correct |
1 ms |
204 KB |
Output is correct |
| 7 |
Correct |
1 ms |
204 KB |
Output is correct |
| 8 |
Correct |
1 ms |
204 KB |
Output is correct |
| 9 |
Correct |
0 ms |
204 KB |
Output is correct |
| 10 |
Correct |
1 ms |
332 KB |
Output is correct |
| 11 |
Runtime error |
1 ms |
460 KB |
Execution killed with signal 11 |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
496 KB |
Output is correct |
| 2 |
Correct |
3 ms |
532 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
844 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
496 KB |
Output is correct |
| 2 |
Correct |
3 ms |
532 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
844 KB |
Execution killed with signal 11 |
| 4 |
Halted |
0 ms |
0 KB |
- |
