Submission #1170159

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170159		jerzyk	Minerals (JOI19_minerals)	C++20	80 / 100	23 ms	3928 KiB

minerals

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000'000'000'000'000'000LL;
const int II = 2'000'000'000;
const ll M = 1000'000'007LL;
const int N = 50'000;
vector<pair<int, int>> ans;
vector<int> nxtp, nxtk;
int aktr = 0;

void DC(bool czyp, bool czyk)
{
    if((int)nxtp.size() == 1)
    {
        //cout << "A: " << nxt[0] << " " << nxt[1] << "\n";
        ans.pb(make_pair(nxtp[0], nxtk[0]));
        return;
    }
    //cout << "DC: " << nxtp.size() << " " << nxtk.size() << "\n";
    int n = (int)nxtp.size();
    int tr = (n + 1) / 2;
    vector<int> poc = nxtp, kon = nxtk;
    vector<int> lp, lk, rp, rk;
    for(int i = 0; i < tr; ++i)
        lp.pb(poc[i]);
    for(int i = tr; i < n; ++i)
        rp.pb(poc[i]);
    if(czyp)
        for(int i = 0; i < (int)rp.size(); ++i)
            aktr = Query(rp[i]);
    else
        for(int i = 0; i < (int)lp.size(); ++i)
            aktr = Query(lp[i]);
    int prev = aktr;
    if(czyk)
    {
        for(int i = 0; i < (int)kon.size(); ++i)
        {
            aktr = Query(kon[i]);
            if(aktr < prev)
                rk.pb(kon[i]);
            else
                lk.pb(kon[i]);
            prev = aktr;
        }
    }else
    {
        for(int i = 0; i < (int)kon.size(); ++i)
        {
            aktr = Query(kon[i]);
            if(aktr > prev)
                rk.pb(kon[i]);
            else
                lk.pb(kon[i]);
            prev = aktr;
        }
    }
    nxtp = lp; nxtk = lk;
    DC(1, czyk ^ 1);

    nxtp = rp; nxtk = rk;
    DC(0, czyk ^ 1);
}

void Solve(int _N)
{
    int n = _N, prev = 0;
    for(int i = 1; i <= 2 * n; ++i)
    {
        aktr = Query(i);
        if(aktr > prev) nxtp.pb(i);
        else nxtk.pb(i);
        prev = aktr;
    }
    DC(1, 1);
    for(int i = 0; i < (int)ans.size(); ++i)
        Answer(ans[i].st, ans[i].nd);
}

• 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: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10