Submission #1248029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248029		Gray	Minerals (JOI19_minerals)	C++20	100 / 100	666 ms	12976 KiB

minerals

#include "minerals.h"
#include <algorithm>
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define ln "\n"

mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());


struct API{
    set<ll> ins; ll val, n;
    vector<ll> perm;
    API(int N){
        val=-1; n=N;
        for (ll i=0; i<n; i++) perm.push_back(i);
        shuffle(perm.begin(), perm.end(), rnd);
    }
    ll getind(ll ind){
        return perm[ind-1]+1;
    }
    bool status(ll ind){
        ind=getind(ind);
        return ins.count(ind)>0;
    }
    void in(ll ind){
        ind=getind(ind);
        if (ins.count(ind)) return;
        val=Query(ind); ins.insert(ind);
    }
    void out(ll ind){
        ind=getind(ind);
        if (!ins.count(ind)) return;
        val=Query(ind); ins.erase(ind);
    }
    ll get(){
        return val;
    }
    // void debug(){
    //     for (auto x:ins)
    // }
};

int n;

void Solve(int N) {
    n=2*N; API com(2*N);
    vector<ll> a, b; int tmp=-1;
    for (ll i=1; i<=n; i++){
        com.in(i);
        int ntmp = com.get();
        if (ntmp!=tmp){
            a.push_back(i);
        }else{
            b.push_back(i);
        }
        tmp=ntmp;
    }
    vector<pair<vector<ll>, vector<ll>>> search, nsearch;
    vector<pair<ll, ll>> res;
    search.push_back({a, b});
    while (!search.empty()){
        set<ll> swps;
        for (auto &[sa, sb]:search){
            // {
            //     for (auto x:sa) cout << x << " ";
            //     cout << endl;
            //     for (auto x:sb) cout << x << " ";
            //     cout << endl << endl;
            // }
            assert(sa.size()==sb.size());
            swap(sa, sb);
            if (sa.size()==1){
                res.push_back({com.getind(sa[0]), com.getind(sb[0])}); continue;
            }
            ll sz=sa.size(), complex=0, complex2=0;
            for (ll i=0; i<sz/2; i++){
                if (!com.status(sa[i])) complex++;
                // com.in(sa[i]);
            }
            for (ll i=sz/2; i<sz; i++){
                if (com.status(sa[i])) complex++;
                // com.out(sa[i]);
            }
            for (ll i=0; i<sz/2; i++){
                if (com.status(sa[i])) complex2++;
                // com.in(sa[i]);
            }
            for (ll i=sz/2; i<sz; i++){
                if (!com.status(sa[i])) complex2++;
                // com.out(sa[i]);
            }
            if (complex<complex2){
                for (ll i=0; i<sz/2; i++){
                    com.in(sa[i]);
                }
                for (ll i=sz/2; i<sz; i++){
                    com.out(sa[i]);
                }
            }else{
                for (ll i=0; i<sz/2; i++){
                    com.out(sa[i]);
                }
                for (ll i=sz/2; i<sz; i++){
                    com.in(sa[i]);
                }
                swps.insert(sa[0]);
            }
        }
        nsearch.clear();
        for (auto &[sa, sb]:search){
            if (sa.size()==1) continue;
            vector<ll> left1, right1, left2, right2;
            ll sz=sa.size();
            for (ll i=0; i<sz/2; i++){
                left1.push_back(sa[i]);
            }
            for (ll i=sz/2; i<sz; i++){
                right1.push_back(sa[i]);
            }
            for (ll i=0; i<(ll)sb.size()-1; i++){
                ll x=sb[i];
                ll prev=com.get();
                if (com.status(x)){
                    com.out(x);
                }else{
                    com.in(x);
                }
                ll cur = com.get();
                if (prev==cur) {
                    if (swps.count(sa[0])) right2.push_back(x);
                    else left2.push_back(x);
                } else {
                    if (!swps.count(sa[0])) right2.push_back(x);
                    else left2.push_back(x);
                }
                if (left1.size()==left2.size()){
                    for (ll j=i+1; j<(ll)sb.size()-1; j++) right2.push_back(sb[j]);
                    break;
                }else if (right1.size()==right2.size()){
                    for (ll j=i+1; j<(ll)sb.size()-1; j++) left2.push_back(sb[j]);
                    break;
                }
            }
            if (left2.size()<right2.size()) left2.push_back(sb.back());
            else right2.push_back(sb.back());
            nsearch.push_back({left1, left2});
            nsearch.push_back({right1, right2});
        }
        swap(search, nsearch);
    }
    for (auto [x, y]:res) Answer(x, y);
}

• 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: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 10 / 10