Submission #1169911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169911		jerzyk	Minerals (JOI19_minerals)	C++20	40 / 100	14 ms	3272 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> nxt;

void DC(bool czy)
{
    if(nxt.size() == 0 || nxt.size() % 2 == 1) return;
    if((int)nxt.size() == 2)
    {
        //cout << "A: " << nxt[0] << " " << nxt[1] << "\n";
        ans.pb(make_pair(nxt[0], nxt[1]));
        if(czy)
            {Query(nxt[0]); Query(nxt[1]);}
        return;
    }
    vector<int> cur = nxt;
    vector<int> l, r;
    int n = cur.size();
    int tr = n / 2;
    if(tr % 2 == 1) ++tr;
    if(!czy)
    {
        int il = 0;
        for(int i = 0; i < n; ++i)
        {
            int a = Query(cur[i]); ++il;
            if(a * 2 > tr)
            {
                r.pb(cur[i]);
                Query(cur[i]); --il;
            }
            else
                l.pb(cur[i]);
        }
    }else
    {
        int il = n;
        for(int i = 0; i < n; ++i)
        {
            int a = Query(cur[i]); --il;
            if(((n / 2) - a) * 2 + (a * 2 - il) * 2 > tr)
            {
                r.pb(cur[i]); ++il;
                Query(cur[i]);
            }
            else
                l.pb(cur[i]);
        }
        swap(l, r);
    }
    nxt = l;
    DC(1);
    nxt = r;
    DC(0);
}

void Solve(int _N)
{
    int n = _N;
    for(int i = 1; i <= 2 * n; ++i)
        nxt.pb(i);
    DC(0);
    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: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10