Submission #501668

#	Time	Username	Problem	Language	Result	Execution time	Memory
501668		79brue	Minerals (JOI19_minerals)	C++14	90 / 100	48 ms	2816 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

int n;
bool chk[100002];
int order[100002], ocnt;
int ans[100002];
bool in[100002];
int lastRet;

int query(int x){
    in[x] = !in[x];
    return Query(order[x]);
}

void solve(int l, int r, vector<int>& vec){
    if(l==r){
        ans[l] = vec[0];
        return;
    }
    int m = (l+r)>>1;
    if(r-m < m-l+1) m--;

    int tmpCalc = 0;
    bool st = 0;
    for(int i=l; i<=m; i++) if(!in[i]) tmpCalc++;
    for(int i=m+1; i<=r; i++) if(in[i]) tmpCalc++;
    if(tmpCalc * 2 > r-l+1) st = 1;

    for(int i=l; i<=m; i++){
        if(in[i] == st) lastRet = query(i);
    }
    for(int i=m+1; i<=r; i++){
        if(in[i] != st) lastRet = query(i);
    }

    vector<int> lVec, rVec;
    for(auto x: vec){
        if((int)lVec.size() == m-l+1){
            rVec.push_back(x);
            continue;
        }
        else if((int)rVec.size() == r-m){
            lVec.push_back(x);
            continue;
        }
        int tmp = query(x);
        if((tmp == lastRet) ^ st) lVec.push_back(x);
        else rVec.push_back(x);
        lastRet = tmp;
    }

    solve(l, m, lVec);
    solve(m+1, r, rVec);
}

void Solve(int N){
    n = N;
    for(int i=1; i<=n+n; i++){
        int tmp = Query(i);
        if(tmp != lastRet) order[++ocnt] = i, chk[i] = 1;
        lastRet = tmp;
        in[i] = 1;
    }
    for(int i=1; i<=n+n; i++) if(!chk[i]) order[++ocnt] = i;
    random_shuffle(order+1, order+n+1);
    random_shuffle(order+n+1, order+n+n+1);

    vector<int> tVec;
    for(int i=n+1; i<=n+n; i++) tVec.push_back(i);
    solve(1, n, tVec);
    for(int i=1; i<=n; i++) Answer(order[i], order[ans[i]]);
}

• 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: 0 / 10