Submission #1129274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129274		OI_Account	Minerals (JOI19_minerals)	C++20	85 / 100	44 ms	3172 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 43000;
const int M = 16;

int n, mark[N + 10], ans[N + 10], last, emp[N + N + 10];
int type[N + N + 10], id1[N + 10], id2[N + 10];
vector<int> good;
int all = 29'728;
mt19937 rng(23);

bool ask(int x) {
    int tmp = Query(x);
    bool res = (tmp != last);
    last = tmp;
    return res;
}

void calcGood() {
    for (int i = 1; i <= n + n; i++)
        if (good.size() < n && ask(i))
            good.push_back(i);
    
}

void calcId() {
    for (auto x: good)
        type[x] = 1;
    for (int i = 1; i <= n + n; i++)
        if (!type[i])
            type[i] = 2;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n + n; i++) {
        if (type[i] == 1)
            id1[++cnt1] = i;
        else
            id2[++cnt2] = i;

    }
    fill(mark + 1, mark + n + 1, true);
}

int calcCnt(int i, int bit) {
    int cnt = 0;
    for (int x = 1; x <= n; x++) {
        bool tmp = ((x & (1 << i))? (bit == 1): (bit == 0));
        if (mark[x] != tmp) 
            cnt++;
    }
    return cnt;
}

int calcMin(int j) {
    //return (all & (1 << j))? 1: 0;
    return calcCnt(j, 0) < calcCnt(j, 1)? 0: 1; 
}

void ask1(int x) {
    ask(id1[x]);
    mark[x] ^= 1;
}

bool ask2(int x) {
    return ask(id2[x]);
}

void changeBit(int i, int bit) {
    for (int x = 1; x <= n; x++) {
        bool tmp = ((x & (1 << i))? (bit == 1): (bit == 0));
        if (mark[x] != tmp) 
            ask1(x);
    }
}

void calcBitAns(int i, int bit, int x) {
    int case1 = ans[x], case2 = ans[x] + (1 << i);
    if (emp[case1] && emp[case2]) {
        if (bit == 1)
            ans[x] += !ask2(x) * (1 << i);
        else 
            ans[x] += (1 - !ask2(x)) * (1 << i);
    }
    else
        ans[x] = (emp[case1]? case1: case2);
    emp[ans[x]]--;
}

void calcBitAns(int i, int bit) {
    vector<int> vec;
    for (int x = 1; x <= n; x++)
        vec.push_back(x);
    shuffle(vec.begin(), vec.end(), rng);
    for (auto x: vec)
        if (ans[x] + (1 << i) <= n) {
            if (true) {
                calcBitAns(i, bit, x);
                continue;
            }
            if (bit == 1)
                ans[x] += !ask2(x) * (1 << i);
            else 
                ans[x] += (1 - !ask2(x)) * (1 << i);
        }
        else
            emp[ans[x]]--;
}

void calcAns() { 
    vector<int> vec;
    /*for (int i = 0; i <= 7; i++) {
        vec.push_back(7 - i);
        vec.push_back(7 + i + 1);
    }*/
    for (int i = 0; i < M; i++)
        vec.push_back(i);
    int all = (1 << M) - 1, t = -1;
    for (auto i: vec) {
        all -= (1 << i);
        int bit = calcMin(i);
        changeBit(i, bit);
        fill(emp + 1, emp + n + 1, 0);
        for (int x = 1; x <= n; x++) {
            emp[x - ((x & all))]++;
        }
        calcBitAns(i, bit);
    }
    /*for (int i = t + 1; i < M; i++) {
        all -= (1 << i);
        int bit = calcMin(i);
        changeBit(i, bit);
        fill(emp + 1, emp + n + 1, 0);
        for (int x = 1; x <= n; x++) {
            emp[x - (x & all)]++;
        }
        calcBitAns(i, bit);
    }*/
    /*for (int i = 0; i >= 0; i--) {
        int bit = calcMin(i);
        changeBit(i, bit);
        calcBitAns(i, bit);
    }*/
}

void writeOutput() {
    for (int i = 1; i <= n; i++)
        Answer(id2[i], id1[ans[i]]);
}

void solve() {
    calcGood();
    calcId();
    calcAns();
    writeOutput();
}

void Solve(int N) {
    n = N;
    solve();
}

/*
4 
1 5 
2 6
3 4 
7 8
*/

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