Submission #250217

#	Time	Username	Problem	Language	Result	Execution time	Memory
250217		dantoh000	Minerals (JOI19_minerals)	C++14	100 / 100	53 ms	3048 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;
vector<int> Q;
vector<int> P;
int ans[86005];
void solve(vector<int> p, int l, int r, int flag){
    if (r == l){
        //printf("%d -> %d\n",Q[l],p[0]);
        Answer(Q[l],p[0]);
        return;
    }
#ifdef debug
    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 m = l +(r-l)*0.38;
    int last;

    for (int i = l; i <= m; i++){
        last = Query(Q[i]);
    }

    for (auto x : p){
        if (Rp.size() == r-m) Lp.push_back(x);
        else if (Lp.size() == m-l+1) Rp.push_back(x);
        else{
            int q = Query(x);
            if ((q == last) != flag){
                Lp.push_back(x);
            }
            else{
                Rp.push_back(x);
            }
            last = q;
        }
    }

    solve(Lp, l, m,  !flag);
    solve(Rp, m+1, r, flag);

}
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;
    }
    solve(P,0,N-1,1);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, int, int, int)':
minerals.cpp:35:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (Rp.size() == r-m) Lp.push_back(x);
             ~~~~~~~~~~^~~~~~
minerals.cpp:36:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         else if (Lp.size() == m-l+1) Rp.push_back(x);
                  ~~~~~~~~~~^~~~~~~~
minerals.cpp:26:9: warning: unused variable 'n' [-Wunused-variable]
     int n = r-l+1;
         ^

• 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