Submission #997592

#	Time	Username	Problem	Language	Result	Execution time	Memory
997592		TimDee	Minerals (JOI19_minerals)	C++17	80 / 100	197 ms	11232 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0; i<(n); ++i)
#define pb push_back
#define pi pair<int,int>
#define f first
#define s second 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int query(int x) {
    return Query(x+1);
}
void Solve(int n) {

    vector<int> in(2*n), c(2*n);
    vector<int> f,s;

    int last=0;
    vector<int> p; forn(i,2*n) p.pb(i);
    shuffle(p.begin(),p.end(),rng);
    forn(i,2*n) {
        if (last==n) {
            s.pb(p[i]); continue;
        }
        int z = query(p[i]);
        if (z > last) f.pb(p[i]);
        else s.pb(p[i]); 
        in[p[i]]=1;
        last = z;
    }

    forn(i,n) c[f[i]]=i;

    vector<pi> v(n);
    forn(i,n) v[i]={0,n-1};

    multiset<int> st;
    forn(i,n) st.insert(n/2);

    vector<vector<int>> ok(n);
    forn(i,n) ok[n/2].pb(i);

    set<int> alive;
    forn(i,n) alive.insert(i);

    vector<vector<int>> other(n);

    int dir = -1;
    int pos=n-1;
    int q2=0;
    while (st.size()) {
        ++q2;

        if (dir == 1) {

            for(auto&x:ok[pos]) {
                st.erase(st.find(pos));
                int l=v[x].f, r=v[x].s;
                if (l==r) continue;
                int m=(l+r+1)>>1;
                int q = query(s[x]);
                int z = -1;
                if (r-l==1) {
                    z = l;
                }
                if (in[s[x]]) {
                    if (q < last) {
                        l = m;
                    } else {
                        r = m-1;
                    }
                } else {
                    if (q > last) {
                        l = m;
                    } else {
                        r = m-1;
                    }
                }
                in[s[x]]^=1;
                last = q;
                v[x] = {l,r};
                m = (l+r+1)>>1;
                if (z!=-1) {
                    int a=other[z][0],b=other[z][1];
                    if (x==a) {
                        if (r==z) v[b]={z+1,z+1};
                        else v[b]={z,z};
                    } else {
                        if (r==z) v[a]={z+1,z+1};
                        else v[a]={z,z};
                    }
                    alive.erase(z);
                    alive.erase(z+1);
                }
                if (l!=r) {
                    ok[m].pb(x);
                    st.insert(m);
                }
                if (r-l==1) {
                    other[l].pb(x);
                }
            }
            ok[pos].clear();

            auto it = st.lower_bound(pos);
            if (it==st.end()) {
                dir*=-1;
                continue;
            }

            last = query(f[pos]);
            auto it2 = alive.upper_bound(pos);
            pos = *it2;

        } else {

            auto it3 = st.upper_bound(pos);
            if (it3!=st.end()) {
                auto it2 = alive.upper_bound(pos);
                pos = *it2;
                dir *= -1; continue;
            }

            last = query(f[pos]);

            for(auto&x:ok[pos]) {
                st.erase(st.find(pos));
                int l=v[x].f, r=v[x].s;
                if (l==r) continue;
                int m=(l+r+1)>>1;
                int q = query(s[x]);
                int z = -1;
                if (r-l==1) {
                    z = l;
                }
                if (in[s[x]]) {
                    if (q < last) {
                        l = m;
                    } else {
                        r = m-1;
                    }
                } else {
                    if (q > last) {
                        l = m;
                    } else {
                        r = m-1;
                    }
                }
                in[s[x]]^=1;
                last = q;
                v[x] = {l,r};
                m = (l+r+1)>>1;
                if (z!=-1) {
                    int a=other[z][0],b=other[z][1];
                    if (x==a) {
                        if (r==z) v[b]={z+1,z+1};
                        else v[b]={z,z};
                    } else {
                        if (r==z) v[a]={z+1,z+1};
                        else v[a]={z,z};
                    }
                    alive.erase(z);
                    alive.erase(z+1);
                }
                if (l!=r) {
                    ok[m].pb(x);
                    st.insert(m);
                }
                if (r-l==1) {
                    other[l].pb(x);
                }
            }
            ok[pos].clear();

            auto it = st.lower_bound(pos);
            if (it == st.begin()) {
                dir *= -1;
                continue;
            }

            auto it2 = alive.lower_bound(pos);
            --it2;
            pos = *it2;
        }
    }
    //cout<<"? "<<q2<<"  ";

    forn(i,n) Answer(s[i]+1,f[v[i].f]+1);

}

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10