Submission #790502

#	Time	Username	Problem	Language	Result	Execution time	Memory
790502		someone	Minerals (JOI19_minerals)	C++14	100 / 100	50 ms	3936 KiB

minerals

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

const int N = 1e5 + 42;

int last = 0, nb;
bool inHand[N];
vector<int> first, second, id;

int send(int i) {
    if(!inHand[i]) {
        inHand[i] = true;
        last = Query(id[i]);
    }
    return last;
}

int getBack(int i) {
    if(inHand[i]) {
        inHand[i] = false;
        last = Query(id[i]);
    }
    return last;
}

int flip(int i) {
    inHand[i] = !inHand[i];
    last = Query(id[i]);
    return last;
}

void print() {/*
    for(int i = 0; i < 2*nb; i++)
        cout << inHand[i];
    cout << ' ' << last << '\n';*/
}

void DPR(vector<int> fi, vector<int> se) {
    if((int)fi.size() == 1 && (int)se.size() == 1) {
        Answer(id[fi[0]], id[se[0]]);
        return;
    }
    if(fi.empty() || se.empty()) {
        //cout << "wtf\n";
        return;
    }
    int diff = 0;
    vector<int> fi1, fi2, se1, se2;
    for(int i = 0; i < (int)fi.size(); i++)
        if(inHand[fi[i]])
            diff++;
        else
            diff--;
    for(int i = 0; i < (int)fi.size(); i++) {
        if(inHand[fi[i]]) {
            if(abs(diff) <= abs(diff - 2)) {
                fi1.push_back(fi[i]);
            } else {
                diff -= 2;
                getBack(fi[i]);
                fi2.push_back(fi[i]);
            }
        } else {
            if(abs(diff) > abs(diff + 2)) {
                diff += 2;
                send(fi[i]);
                fi1.push_back(fi[i]);
            } else {
                fi2.push_back(fi[i]);
            }
        }
    }

    for(int j : se) {
        int nbType = last;
        if(se1.size() == fi1.size()) {
            se2.push_back(j);
        } else if(se2.size() == fi2.size()) {
            se1.push_back(j);
        } else if(flip(j) == nbType) {
            se1.push_back(j);
        } else {
            se2.push_back(j);
        }
    }
    fi.clear();
    se.clear();
    DPR(se1, fi1);
    DPR(se2, fi2);
}

void Solve(int n) {
    nb = n;
    int nbType = 0;
    mt19937 rng(43);
    for(int i = 1; i <= 2*n; i++)
        id.push_back(i);
    shuffle(id.begin(), id.end(), rng);
    for(int i = 0; i < 2*n; i++) {
        if(send(i) == nbType) {
            second.push_back(i);
        } else {
            nbType++;
            first.push_back(i);
        }
    }
    DPR(first, second);
}

• 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