Submission #1129045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129045		OI_Account	Minerals (JOI19_minerals)	C++20	6 / 100	2 ms	672 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;
int type[N + N + 10], id1[N + 10], id2[N + 10];
vector<int> good;

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 (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 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) {
    for (int x = 1; x <= n; x++)
        if (ans[x] + (1 << i) <= n) {
            if (bit == 0)
                ans[x] += ask2(x) * (1 << i);
            else 
                ans[x] += (1 - ask2(x)) * (1 << i);
        }
}

void calcAns() {
    for (int i = M - 2; i >= 0; i--) {
        int bit = calcMin(i);
        changeBit(i, bit);
        calcBitAns(i, bit);
    }
    for (int i = M - 1; i >= M - 1; 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: 0 / 25
• Subtask 3: 0 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10