Submission #376875

#	Time	Username	Problem	Language	Result	Execution time	Memory
376875		wiwiho	Minerals (JOI19_minerals)	C++14	40 / 100	160 ms	4456 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>;
using pii = pair<int, int>;
 
ostream& operator<<(ostream& o, pll p){
    return o << '(' << p.F << ',' << p.S << ')';
}
 
vector<int> t;
vector<int> ans;
vector<pii> rng;

set<int> ma;
int query(int i){
    if(ma.find(i) == ma.end()) ma.insert(i);
    else ma.erase(i);
    return Query(i);
}

int n;
 
void dothing(int l, int r){
    set<int> oao;
    for(int i = l; i <= r; i++){
        oao.insert(t[i]);
    }
    set<int> del;
    for(int i : ma){
        if(oao.find(i) == oao.end()) del.insert(i);
    }
    for(int i : del) query(i);
    for(int i : oao) if(ma.find(i) == ma.end()) query(i);
    //cerr << l << " " << r << "  ";
    //printv(ma, cerr);
}
 
void check(int cnt, vector<int>& now, vector<int>& yes, vector<int>& no, int l, int r){
    for(int i : now){
        if(rng[i].S < l || r < rng[i].F){
            no.eb(i);
            continue;
        }
        int rs = query(i);
        //cerr << "check " << l << " " << r << " " << i << " " << rng[i] << " " << rs << "\n";
        if(rs == 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);
    //cerr << "ma ";
    //printv(ma, cerr);
    vector<int> yes, no;
    check(m - l + 1, now, yes, no, l, m);
    vector<int>().swap(now);
    bs(l, m, yes);
    bs(m + 1, r, no);
}
 
void Solve(int _n){
    n = _n;
 
    vector<int> now;
    ans.resize(2 * n + 1, -1);
    rng.resize(2 * n + 1);
    for(int i = 1; i <= 2 * n; i++){
        int r = query(i);
        if(r != t.size() + 1){
            now.eb(i);
            query(i);
            rng[i] = mp(0, (int)t.size() - 1);
        }
        else t.eb(i);
    }
    //printv(now, cerr);
    //printv(t, cerr);
    //printv(rng, cerr);
    for(int i : t) 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:96:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         if(r != t.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