Submission #997388

#	Time	Username	Problem	Language	Result	Execution time	Memory
997388		12345678	Minerals (JOI19_minerals)	C++17	75 / 100	26 ms	2900 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=5e4+5;

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();
    //cout<<"solve "<<sz<<'\n';
    //for (int i=0; i<sz; i++) cout<<i<<' '<<l[i]<<' '<<r[i]<<'\n';
    if (sz==1) return Answer(l[0], r[0]), void();
    int md=(sz-1)/2;
    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 (update(r[i])==t) l2.push_back(r[i]);
        else r2.push_back(r[i]); 
    }
    //cout<<"debug "<<l1.size()<<' '<<l2.size()<<' '<<r1.size()<<' '<<r2.size()<<'\n';
    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);
}

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

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10