Submission #997653

#	Time	Username	Problem	Language	Result	Execution time	Memory
997653		TimDee	Minerals (JOI19_minerals)	C++17	100 / 100	34 ms	3384 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int nx=5e4+5;
 
mt19937 rng(time(0));
 
int p, c;
vector<int> l, r;
 
 
int update(int x)
{
    p=Query(x);
    swap(c, p);
    return c!=p;
}
 
void solve(vector<int> &l, vector<int> &r, int t)
{
    int sz=l.size();
    if (sz==1) return Answer(l[0], r[0]), void();
    int md=(int)(0.4*sz);
    vector<int> l1, l2, r1, r2;
    for (int i=0; i<=md; i++) l1.push_back(l[i]), update(l[i]);
    for (int i=md+1; i<sz; i++) r1.push_back(l[i]);
    for (int i=0; i<sz; i++)
    {
        if (l2.size()==l1.size()) r2.push_back(r[i]);
        else if (r2.size()==r1.size()) l2.push_back(r[i]);
        else if (update(r[i])==t) l2.push_back(r[i]);
        else r2.push_back(r[i]); 
    }
    solve(l1, l2, !t); solve(r1, r2, t);
}
 
void Solve(int N) {
    for (int i=1; i<=2*N; i++) 
    {
        if (update(i)) l.push_back(i);
        else r.push_back(i);
    }
    solve(l, r, 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