//
// --- Sample implementation for the task swaps ---
//
// To compile this program with the sample grader, place:
// swaps.h swaps_sample.cpp sample_grader.cpp
// in a single folder and run:
// g++ swaps_sample.cpp sample_grader.cpp
// in this folder.
//
#include "swaps.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)((x).size())
#define pb push_back
#define MX(a,b) a = max(a,b)
#define MN(a,b) a = min(a,b)
#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT
const int maxn = 500+6;
vector<int> val[maxn];
int IT = 0;
vector<int> bank;
int sche(int a, int b){
schedule(a,b);
return IT++;
}
struct sg{
vector<int> v;
bool state;
vector<int> where;
vector<int> ga, gb; // group a, group b
void splitask(){
where.clear();
for (int i = 0; i+1< SZ(v); i+=2) {
where.pb(sche(v[i],v[i+1]));
bug(SZ(where));
}
}
void splitget(){
// bug("yo");
for (int i = 0; i+1< SZ(v); i+=2) {
// bug(i/2, SZ(where));
// bug(where[i/2], SZ(bank));
if (bank[where[i/2]]) {
// means the first one is bigger
ga.pb(v[i]); gb.pb(v[i+1]);
}else{
ga.pb(v[i+1]); gb.pb(v[i]);
}
}
}
void destruct(){
bug ("Splitting into: ");
// for (int x : ga) cout<<x<<' ';
// cout<<endl;
// for (int x : gb) cout<<x<<' ';
// cout<<endl;
bug("OK!");
// if (SZ(v) % 2 == 0) {
// splittable, smaller ones get rank bump
for (int x : gb) {
val[x].back()++;
}
// }
}
void lastask(){
where.clear();
where.pb(sche(gb.back(), v.back()));
}
void lastget(){
ga.pb(v.back());
if (bank[where[0]]) {
// gb.back() is bigger
swap(gb.back(), ga.back());
}else{
}
}
sg(vector<int> ss) {
v = ss;
state = 0;
}
};
struct fren{
vector<sg> s;
vector<int> v;
void ask(){
for (sg &t : s) {
if (t.state == 0) {
t.splitask();
}else{
t.lastask();
}
}
}
void get(){
vector<sg> nw;
for (sg &t : s) {
if (t.state == 0) {
t.splitget();
}else{
t.lastget();
}
if (SZ(t.v) % 2 == 0 || t.state) {
// split time
t.destruct();
bug("Split time!", SZ(t.ga), SZ(t.gb));
if (SZ(t.ga) > 1) {
nw.pb(sg(t.ga));
}
if (SZ(t.gb) > 1) {
nw.pb(sg(t.gb));
}
}else{
t.state = 1;
nw.pb(t);
}
}
s.swap(nw);
bug(SZ(s));
}
fren(sg sss, vector<int> vvv){
s = {sss};
v = vvv;
}
};
void solve(int n, int V) {
// TODO implement this function
vector<fren> fb;
{
vector<int> tmp;
REP1(i,n) {
tmp.pb(i); val[i].pb(0);
}
fb.pb(fren(sg(tmp), tmp));
}
REP(ja, V) {
if (SZ(fb) == 0) break;
if (ja == V-1) assert(0);
IT = 0;
{
for (fren &f : fb) {
f.ask();
}
}
bug(IT);
bank = visit();
{
vector<fren> newf;
for (fren &f : fb) {
f.get();
if (SZ(f.s) == 0) {
map<int, vector<int> > mp;
int smol = 10000000; int big = -1;
for (int x : f.v) {
MN(smol, val[x].back());
MX(big, val[x].back());
}
for (int x : f.v) {
int y;
if (val[x].back() == smol) y = -1;
else if (val[x].back()==big) y = 1;
else y = 0;
val[x].back() = y;
mp[y].pb(x);
// bug(val[x].back());
}
// int smol = mp.begin()->f;
for (auto tt : mp) {
if (SZ(tt.s) > 1) {
for( int y : tt.s) val[y].pb(0);
newf.pb(fren(sg(tt.s),tt.s));
}
}
}else{
newf.pb(f);
}
}
fb.swap(newf);
}
// bug("F sizes: ");
// for (fren ff : fb) {
// cout<<SZ(ff.v)<<' ';
// }
// cout<<endl;
}
vector<int> yay;
REP1(i,n) {
// cout<<i<<": ";
// for (int x : val[i]) cout<<x<<' ';
// cout<<endl;
yay.pb(i);
}
sort(ALL(yay), [&](int a, int b) {return val[a] < val[b];});
answer(yay);
}
/*
5 1000
2 1 5 4 3
0
0
11 100
1 8 3 9 10 11 6 4 2 5 7
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Correct |
| 2 |
Incorrect |
9 ms |
348 KB |
Not correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
200 KB |
Correct |
| 2 |
Incorrect |
9 ms |
328 KB |
Not correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
200 KB |
Not correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
