Submission #120718

#	Time	Username	Problem	Language	Result	Execution time	Memory
120718		onjo0127	Minerals (JOI19_minerals)	C++14	100 / 100	53 ms	3236 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;

bool chk[100009];

int query(int x) {
    chk[x] = !chk[x];
    //printf("query x: %d\n", x);
    return Query(x);
}

void answer(int a, int b) {
    //printf("answer: (%d, %d)\n", a, b);
    Answer(a, b);
}

pair<vi, vi> split(int N) {
    vector<int> A, B;
    int pr = 0, i = 0;
    for(i=1; i<=2*N; i++) {
        int Q = query(i);
        if(pr != Q) A.push_back(i);
        else B.push_back(i);
        pr = Q;
    }
    return {A, B};
}

void go(vector<int> &A, vector<int> &B, bool AC) {
    //puts("AB");
    //for(auto& it: A) printf("%d ",it); puts("");
    //for(auto& it: B) printf("%d ",it); puts("");
    int N = A.size();
    if(N == 1) {
        answer(A[0], B[0]);
        return;
    }
    vector<int> LA, RA, LB, RB;
    int m = N/2, pr;
    if(!AC) {
        if(N >= 10) m = N - (int)(1.0*N/1.618);
        for(int i=0; i<m; i++) {
            pr = query(A[i]);
            LA.push_back(A[i]);
        }
        for(int i=m; i<N; i++) RA.push_back(A[i]);
    }
    if(AC) {
        if(N >= 10) m = (int)(1.0*N/1.618);
        for(int i=N-1; i>=m; i--) {
            pr = query(A[i]);
            RA.push_back(A[i]);
        }
        for(int i=0; i<m; i++) LA.push_back(A[i]);
    }
    int i;
    for(i=0; i<N; i++) {
        int Q = query(B[i]);
        if(pr != Q) RB.push_back(B[i]);
        else LB.push_back(B[i]);
        if(RB.size() == RA.size()) break;
        if(LB.size() == LA.size()) break;
        pr = Q;
    }
    if(RB.size() == RA.size()) for(++i; i<N; i++) LB.push_back(B[i]);
    else for(++i; i<N; i++) RB.push_back(B[i]);
    go(LA, LB, 1);
    go(RA, RB, 0);
}

void Solve(int N) {
    vi A, B; tie(A, B) = split(N);
    go(A, B, 1);
}

Compilation message (stderr)

minerals.cpp: In function 'void go(std::vector<int>&, std::vector<int>&, bool)':
minerals.cpp:61:9: warning: 'pr' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if(pr != Q) RB.push_back(B[i]);
         ^~

• 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