Submission #250090

#	Time	Username	Problem	Language	Result	Execution time	Memory
250090		dantoh000	Minerals (JOI19_minerals)	C++14	40 / 100	32 ms	2420 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){
    if (r == l){
        //printf("%d -> %d\n",Q[l],p[0]);
        ans[Q[l]] = p[0];
        return;
    }
    /*printf("new\n");
    for (auto x : p){
        printf("%d ",x);
    }
    printf("<- P\n");
    for (int i = l; i <= r; i++){
        printf("%d ",Q[i]);
    }
    printf("<- Q\n");*/
    assert(p.size() == r-l+1);
    vector<int> Lp;
    vector<int> Rp;
    int n = r-l+1;
    int mid = (l+r)/2;
    int last;
    for (int i = mid+1; i <= r; i++){
        //printf("solve: removing %d\n",Q[i]);
        last = Query(Q[i]);
    }
    for (int i = 0; i < n; i++){
        //printf("solve: removing %d\n",p[i]);
        int q = Query(p[i]);
        if (q == last){
            //printf("solve: adding %d\n",p[i]);
            Query(p[i]);
            Lp.push_back(p[i]);
        }
        else{
            Rp.push_back(p[i]);
        }
       last = q;
    }
    solve(Lp, l, mid);
    for (auto x : p) {
        //printf("solve: removing/adding %d\n",x);
        Query(x);
    }
    for (int i = l; i <= r; i++) {
        //printf("solve: removing/adding %d\n",Q[i]);
        Query(Q[i]);
    }
    solve(Rp, mid+1, r);
}
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);
    for (auto x: Q){
        Answer(x,ans[x]);
    }
}

Compilation message (stderr)

In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from minerals.cpp:1:
minerals.cpp: In function 'void solve(std::vector<int>, int, int)':
minerals.cpp:22:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     assert(p.size() == r-l+1);
            ~~~~~~~~~^~~~~~~~
minerals.cpp:35:9: warning: 'last' may be used uninitialized in this function [-Wmaybe-uninitialized]
         if (q == last){
         ^~

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