Submission #250179

#	Time	Username	Problem	Language	Result	Execution time	Memory
250179		dantoh000	Minerals (JOI19_minerals)	C++14	90 / 100	81 ms	3924 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 verdict;
int query(int x){
    ON[x] ^= 1;
    verdict = ON[x];
    return Query(x);
}
void solve(vector<int> p, vector<int> q){
    if (p.size() == 1){
        Answer(q[0],p[0]);
        return;
    }
    /*else if (p.size() == 2){
        printf("settle <%d,%d> <-> <%d,%d>\n",q[0],q[1],p[0],p[1]);
        //printf("last query %d\n",last);
        int q1;
        int qon, qoff, On, Off;
        if (ON[q[0]]^ON[q[1]]) {
            qon = ON[q[0]]?q[0]:q[1];
            qoff = ON[q[0]]?q[1]:q[0];
            q1 = -1;
        }
        else{
            q1 = query(q[0]);
            qon = ON[q[0]]?q[0]:q[1];
            qoff = ON[q[0]]?q[1]:q[0];
        }
        assert(ON[qon] && !ON[qoff]);
        if (ON[p[0]] ^ ON[p[1]]){
            On = ON[p[0]]?p[0]:p[1];
            Off = ON[p[0]]?p[1]:p[0];
            if (q1 == -1){
                q1 = query(On);
                if (q1 == last){
                    Answer(qon, On);
                    Answer(qoff, Off);
                }
            }
            else if (q1 == last){
                Answer(qon,On);
                Answer(qoff,Off);
            }
            else{
                Answer(qon,Off);
                Answer(qoff,On);
            }
            last = q1;
            return;
        }
        if (q1 == -1){
            q1 = query(p[0]);
            On = ON[p[0]]?p[0]:p[1];
            Off = ON[p[0]]?p[1]:p[0];
            if ((verdict == 0) ^ (q1 == last)){
                Answer(qon,On);
                Answer(qoff,Off);
            }
            else{
                Answer(qoff,On);
                Answer(qon,Off);
            }
            last = q1;
            return;
        }
        else last = q1;
        q1 = query(p[0]);
        On = ON[p[0]]?p[0]:p[1];
        Off = ON[p[0]]?p[1]:p[0];
        if ((verdict == 0) ^ (q1 == last)){
            Answer(qon,On);
            Answer(qoff,Off);
        }
        else{
            Answer(qoff,On);
            Answer(qon,Off);
        }
        last = q1;
        return;
    }*/
#ifdef debug
    for (auto x : p){
        printf("%d ",x);
    }
    printf("<- P\n");
    for (auto x : q){
        printf("%d ",x);
    }
    printf("<- P\n");
#endif
    assert(p.size() == q.size());
    vector<int> Lp;
    vector<int> Rp;
    vector<int> Lq, Rq;
    int n = q.size();
    int mid = n/2;
    for (auto x : q){
        if (ON[x]){
            if (Lq.size() == mid){
                last = query(x);
                Rq.push_back(x);
            }
            else{
                Lq.push_back(x);
            }
        }
        else{
            if (Rq.size() == q.size()-mid){
                last = query(x);
                Lq.push_back(x);
            }
            else{
                Rq.push_back(x);
            }
        }
    }
    for (int i = 0; i < n; i++){
        int q = query(p[i]);
        if (q == last){
            //printf("%d goes left\n",p[i]);
            Lp.push_back(p[i]);
        }
        else{
            //printf("%d goes right\n",p[i]);
            Rp.push_back(p[i]);
        }
        last = q;
        if (Lp.size() == Lq.size() || Rp.size() == Rq.size()){
            //printf("ALL FILLED\n");
            for (int j = i+1; j < n; j++){
                if (Lp.size() == Lq.size()) 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, Lq);
    solve(Rp, Rq);


}
void Solve(int N) {
    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,Q);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>)':
minerals.cpp:105:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (Lq.size() == mid){
                 ~~~~~~~~~~^~~~~~

• 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