Submission #997569

#	Time	Username	Problem	Language	Result	Execution time	Memory
997569		TimDee	Minerals (JOI19_minerals)	C++17	75 / 100	195 ms	11364 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 

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

    if (0 && 4*n*n <= 1000000) {
        for(int i=0; i<2*n; ++i) {
            query(i);
            for(int j=i+1; j<2*n; ++j) {
                int x = query(j);
                //cout<<"? "<<i<<' '<<j<<' '<<x<<'\n';
                if (x>1) query(j);
                else {
                    Answer(i+1,j+1);
                    query(j);
                    break;
                }
            }
            query(i);
        }
        return;
    }

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

    int last=0;
    forn(i,2*n) {
        int z = query(i);
        if (z > last) f.pb(i);
        else s.pb(i); 
        in[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);
    //cout<<"f: "; for(auto&x:f) cout<<x<<' '; cout<<'\n';
    //cout<<"s: "; for(auto&x:s) cout<<x<<' '; cout<<'\n';
    //return;

    int dir = -1;
    int pos=n-1;
    while (st.size()) {
        //cout<<"? "<<pos<<' '<<dir<<'\n'; cout.flush();
        //for(auto&x:st) cout<<x<<' '; cout<<'\n';
        //for(auto&x:alive) cout<<x<<' '; cout<<'\n';
        //cout.flush();

        if (dir == 1) {

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

            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) {
                    assert(l==r);
                    int a=other[z][0],b=other[z][1];
                    assert(x==a || x==b);
                    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();

            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 it = st.lower_bound(pos);
            if (it == st.begin() && (*it) > pos) {
                assert(0);
                dir *= -1;
                continue;
            }

            last = query(f[pos]);

            for(auto&x:ok[pos]) {
                //cout<<"??? "<<pos<<' '<<x<<'\n'; cout.flush();
                //cout<<st.size()<<'\n';
                //for(auto&x:st) cout<<x<<' '; cout<<'\n'; cout.flush();
                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;
                }
                //cout<<"? "<<pos<<' '<<x<<' '<<s[x]<<' '<<in[s[x]]<<' '<<last<<' '<<q<<'\n';
                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) {
                    assert(l==r);
                    int a=other[z][0],b=other[z][1];
                    //cout<<"?! "<<z<<' '<<a<<' '<<b<<"  "<<x<<' '<<l<<' '<<r<<'\n';
                    assert(x==a || x==b);
                    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();
            //cout<<"? "<<pos<<'\n'; cout.flush();

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

            auto it2 = alive.lower_bound(pos);
            --it2;
            pos = *it2;
        }
    }

    //forn(i,n) cout<<s[i]<<": "<<v[i].f<<' '<<v[i].s<<'\n';
    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: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10