Submission #477670

#	Time	Username	Problem	Language	Result	Execution time	Memory
477670		HappyPacMan	Minerals (JOI19_minerals)	C++14	100 / 100	88 ms	3028 KiB

minerals

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

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int curr = 0;

bool change(int u){
    int nxt = Query(u);
    bool res = (nxt != curr);
    curr = nxt;
    return res;
}

void rec(vector<int> &A,vector<int> &B,bool rev){
    int len = A.size();
    if(len == 1){
        Answer(A[0],B[0]);
        return;
    }
    shuffle(A.begin(),A.end(),rng);
    shuffle(B.begin(),B.end(),rng);
    int mid = (rev?382:618)*len/1000;
    if(mid == 0) mid++;
    if(mid == len) mid--;
    vector<int> nA[2],nB[2];
    for(int i=0;i<len;i++){
        if(i < mid) nA[0].push_back(A[i]);
        else nA[1].push_back(A[i]);
        if((mid <= i) ^ rev) change(A[i]);
    }
    for(int i=0;i<len;i++){
        if(nB[0].size() == nA[0].size()) nB[1].push_back(B[i]);
        else if(nB[1].size() == nA[1].size()) nB[0].push_back(B[i]);
        else if(change(B[i])) nB[0].push_back(B[i]);
        else nB[1].push_back(B[i]);
    }
    rec(nA[0],nB[0],0);
    rec(nA[1],nB[1],1);
}

void Solve(int N){
    vector<int> group[2];
    for(int i=1;i<=2*N;i++) group[change(i)].push_back(i);
    rec(group[0],group[1],1);
}

• 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