제출 #250150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250150		dantoh000	Minerals (JOI19_minerals)	C++14	90 / 100	60 ms	3556 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
vector<int> Q;
vector<int> P;
int ans[86005];
int ON[86005];
int last;
int query(int x){
    ON[x] ^= 1;
    return Query(x);
}
void solve(vector<int> p, int l, int r, int flag){

    if (r == l){
        Answer(Q[l],p[0]);
        return;
    }
    else if (l + 1 == r){
        //printf("last query %d\n",last);
        int q1;
        if (flag) q1 = query(Q[r]);
        else q1 = query(Q[l]);
        assert(ON[Q[l]] && !ON[Q[r]]);
        if (ON[p[0]] ^ ON[p[1]]){
            //printf("-----------------------------------------TWO\n");
            //printf("%d %d <-> %d %d\n",Q[l],Q[r],p[0],p[1]);
            //printf("flag = %d, q1 = %d, last = %d\n",flag,q1,last);
            int On = ON[p[0]]?0:1;
            int Off = 1^On;
            On = p[On], Off = p[Off];
            if ((q1 == last) ^ flag){
                Answer(Q[l],On);
                Answer(Q[r],Off);
            }
            else{
                Answer(Q[l],Off);
                Answer(Q[r],On);
            }
            last = q1;
            return;
        }
        last = q1;
        q1 = query(p[0]);
        if ((q1 == last)) ans[Q[l]] = p[0], ans[Q[r]] = p[1];
        else ans[Q[l]] = p[1], ans[Q[r]] = p[0];
        Answer(Q[l],ans[Q[l]]);
        Answer(Q[r],ans[Q[r]]);
        last = q1;
        return;
    }
#ifdef debug
    printf("new <%d,%d> %d\n",l,r,flag);
    for (auto x : p){
        printf("%d ",x);
    }
    printf("<- P\n");
    for (int i = l; i <= r; i++){
        printf("%d ",Q[i]);
    }
    printf("<- Q\n");
#endif
    //assert(p.size() == r-l+1);
    vector<int> Lp;
    vector<int> Rp;
    int n = r-l+1;
    int mid;
    mid = (l+r)/2;
    if (flag){
        for (int i = mid+1; i <= r; i++){
            last = query(Q[i]);
        }
    }
    else{
        for (int i = l; i <= mid; i++){
            last = query(Q[i]);
        }
    }

    for (int i = 0; i < n; i++){
        int q = query(p[i]);
        if (q == last){
            Lp.push_back(p[i]);
        }
        else{
            Rp.push_back(p[i]);
        }
        last = q;
        if (Lp.size() == mid-l+1 || Rp.size() == r-mid){
            //printf("ALL FILLED\n");
            for (int j = i+1; j < n; j++){
                if (Lp.size() == mid-l+1) Rp.push_back(p[j]);
                else Lp.push_back(p[j]);
            }
            break;
        }

    }
#ifdef debug
    printf("Lp: ");
    for (auto x : Lp) printf("%d ",x);
    printf("\n");
    printf("Rp: ");
    for (auto x : Rp) printf("%d ",x);
    printf("\n");
#endif

    solve(Lp, l, mid, 1);
    solve(Rp, mid+1, r, 0);


}
void Solve(int N) {
    int last = 0;
    for (int i = 1; i <= 2*N; i++){
        int q = query(i);
        if (q == last){
            Q.push_back(i);
        }
        else{
            P.push_back(i);
        }
        last = q;
        ON[i] = 1;
    }
    srand(time(NULL));
    random_shuffle(Q.begin(),Q.end());
    random_shuffle(P.begin(),P.end());
    solve(P,0,N-1,1);
}

컴파일 시 표준 에러 (stderr) 메시지

minerals.cpp: In function 'void solve(std::vector<int>, int, int, int)':
minerals.cpp:89:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (Lp.size() == mid-l+1 || Rp.size() == r-mid){
             ~~~~~~~~~~^~~~~~~~~~
minerals.cpp:89:47: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (Lp.size() == mid-l+1 || Rp.size() == r-mid){
                                     ~~~~~~~~~~^~~~~~~~
minerals.cpp:92:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (Lp.size() == mid-l+1) Rp.push_back(p[j]);
                     ~~~~~~~~~~^~~~~~~~~~

• 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: 0 / 10