Submission #625092

#	Time	Username	Problem	Language	Result	Execution time	Memory
625092		Do_you_copy	Minerals (JOI19_minerals)	C++17	90 / 100	57 ms	2516 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
#define taskname "test"
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

//const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e5 + 1;

int n;

vector <int> a, b;
int cur = 0;
bool open[maxN];
ll cntt =0;
void parallel_bs(vector <int> &w, int l = 1, int r = n){
    if (l == r){
        Answer(w.back(), a[l]);
        w.clear();
        return;
    }
    int mid = (l + r) / 2;
    int last = 0;
    int cntl1, cntl2, cntr1, cntr2;
    cntl1 = cntl2 = cntr1 = cntr2 = 0;
    for (int i = l; i <= mid; ++i){
        if (open[a[i]]){
            ++cntl1;
        }
    }
    for (int i = mid + 1; i <= r; ++i){
        if (!open[a[i]]){
            ++cntr1;
        }
    }
    cntl2 = mid - l + 1 - cntl1;
    cntr2 = r - mid - cntr1;
    bool flag = 0;
    int tem1[] = {mid - l + 1, r - mid};
    if (cntl1 + cntr1 > cntl2 + cntr2) flag = 1;
    for (int i = l; i <= mid; ++i){
        if (open[a[i]] ^ flag){
            open[a[i]] = 1 ^ open[a[i]];
            ++cntt;
            last = Query(a[i]);
        }
    }
    for (int i = mid + 1; i <= r; ++i){
        if (!open[a[i]] ^ flag){
            open[a[i]] = 1 ^ open[a[i]];
            ++cntt;
            last = Query(a[i]);
        }
    }
    vector <int> left, right;
    int _ = 0;
    random_shuffle(w.begin(), w.end());
    if (l == 1 && r == 2) cerr << w[0] << " ";
    for (_ = 0; _ < w.size(); ++_){
        int i = w[_];
        int tem = Query(i);
        open[i] ^= 1;
        if (last == tem) left.pb(i);
        else right.pb(i);
        if (left.size() == tem1[1 ^ flag] || right.size() == tem1[0 ^ flag]) break;
        last = tem;
    }
    ++_;
    if (left.size() == tem1[1 ^ flag]){
        for (; _ < w.size(); ++_){
            int i = w[_];
            right.pb(i);
        }
    }
    else if (right.size() == tem1[0 ^ flag]){
        for (; _ < w.size(); ++_){
            int i = w[_];
            left.pb(i);
        }
    }
    if (!flag) swap(left, right);
    //cerr << l << " " << r << " " << mid << " " << left.size() << " " << right.size() << "\n";
    //assert(right.size() == tem1[1 ^ flag]);
    w.clear();
    parallel_bs(left, l, mid);
    parallel_bs(right, mid + 1, r);
}

void Solve(int N){
    n = N;
    int last = 0;
    a.pb(0);
    for (int i = 1; i <= 2 * n; ++i){
        int tem = Query(i);
        if (tem > last) a.pb(i);
        else b.pb(i);
        last = tem;
    }
    fill (open, open + 2 * n + 1, 1);
    parallel_bs(b, 1, n);
    cerr << cntt << " ";
}

Compilation message (stderr)

minerals.cpp: In function 'void parallel_bs(std::vector<int>&, int, int)':
minerals.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (_ = 0; _ < w.size(); ++_){
      |                 ~~^~~~~~~~~~
minerals.cpp:86:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if (left.size() == tem1[1 ^ flag] || right.size() == tem1[0 ^ flag]) break;
      |             ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
minerals.cpp:86:59: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |         if (left.size() == tem1[1 ^ flag] || right.size() == tem1[0 ^ flag]) break;
      |                                              ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
minerals.cpp:90:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   90 |     if (left.size() == tem1[1 ^ flag]){
      |         ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
minerals.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         for (; _ < w.size(); ++_){
      |                ~~^~~~~~~~~~
minerals.cpp:96:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   96 |     else if (right.size() == tem1[0 ^ flag]){
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
minerals.cpp:97:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for (; _ < w.size(); ++_){
      |                ~~^~~~~~~~~~

• 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