제출 #501635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
501635		qwerasdfzxcl	Minerals (JOI19_minerals)	C++14	70 / 100	42 ms	2236 KiB

minerals

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

using namespace std;
typedef long long ll;
mt19937_64 rng(69), rng2(74);

void Solve(int N) {
    vector<int> A, B, ans(N), on(N);

    int cur = 0;
    for (int i=1;i<=N*2;i++){
        int tmp = Query(i);
        if (tmp>cur) A.push_back(i);
        else B.push_back(i);
        cur = tmp;
    }

    shuffle(A.begin(), A.end(), rng);
    shuffle(B.begin(), B.end(), rng2);

    int cnt = 0;
    for (int i=0;i<N;i++) if (!(i&1)){
        on[i] ^= 1;
        if (on[i]) cnt++;
        else cnt--;

        cur = Query(B[i]);
    }

    //printf("YES\n");

    for (int j=0;j<16;j++){
        int cnt2 = 0;
        for (int i=0;i<N;i++){
            int tmp = Query(A[i]);
            if (tmp==cur) ans[i] |= 1<<j, cnt2++;
            cur = tmp;
            if (cnt2==cnt) break;
        }

        if (j==15) break;
        for (int i=0;i<N;i++) if (((i>>j)&1) ^ ((i>>(j+1))&1)){
            on[i] ^= 1;
            if (on[i]) cnt++;
            else cnt--;

            cur = Query(B[i]);
        }
    }

    //for (int i=0;i<N;i++) printf("%d ", ans[i]);

    for (int i=0;i<N;i++) Answer(A[i], B[ans[i]]);
}

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