Submission #376748

#	Time	Username	Problem	Language	Result	Execution time	Memory
376748		wiwiho	Minerals (JOI19_minerals)	C++14	40 / 100	28 ms	2284 KiB

minerals

#include "minerals.h"

#include<bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define eb emplace_back

using namespace std;

typedef long long ll;

using pll = pair<ll, ll>;

ostream& operator<<(ostream& o, pll p){
    return o << '(' << p.F << ',' << p.S << ')';
}

vector<int> t;
vector<int> ans;

void dothing(int l, int r){
    for(int i = l; i <= r; i++) Query(t[i]);
}

void check(int cnt, vector<int>& now, vector<int>& yes, vector<int>& no){
    for(int i : now){
        int r = Query(i);
        if(r == cnt) yes.eb(i);
        else no.eb(i);
        Query(i);
    }
}

void bs(int l, int r, vector<int>& now){
    if(l > r || now.empty()) return;
    //cerr << "bs " << l << " " << r << "  ";
    //printv(now, cerr);
    if(l == r){
        for(int i : now) ans[i] = t[l];
        return;
    }
    int m = (l + r) / 2;
    dothing(l, m);
    vector<int> yes, no;
    check(m - l + 1, now, yes, no);
    dothing(l, m);
    vector<int>().swap(now);
    bs(l, m, yes);
    bs(m + 1, r, no);
}

void Solve(int n){

    vector<int> now;
    ans.resize(2 * n + 1, -1);
    for(int i = 1; i <= 2 * n; i++){
        int r = Query(i);
        if(r != now.size() + 1){
            t.eb(i);
            Query(i);
        }
        else now.eb(i);
    }
    //printv(now, cerr);
    //printv(t, cerr);
    for(int i : now) Query(i);

    vector<int> tnow = now;
    bs(0, n - 1, tnow);
    //printv(ans, cerr);
    for(int i : now){
        Answer(i, ans[i]);
    }

}

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:66:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         if(r != now.size() + 1){
      |            ~~^~~~~~~~~~~~~~~~~

• 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