Submission #418138

#	Time	Username	Problem	Language	Result	Execution time	Memory
418138		balbit	The Collection Game (BOI21_swaps)	C++14	0 / 100	9 ms	348 KiB

swaps

//
// --- 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

*/

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 3
• Subtask 4: 0 / 2
• Subtask 5: 0 / 9
• Subtask 6: 0 / 6
• Subtask 7: 0 / 9
• Subtask 8: 0 / 6
• Subtask 9: 0 / 21
• Subtask 10: 0 / 14
• Subtask 11: 0 / 9
• Subtask 12: 0 / 6