Submission #624924

#	Time	Username	Problem	Language	Result	Execution time	Memory
624924		Do_you_copy	Minerals (JOI19_minerals)	C++17	90 / 100	42 ms	2500 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;
    for (int i = l; i <= mid; ++i){
        if (open[a[i]]){
            open[a[i]] = 0;
            last = Query(a[i]);
        }
    }
    for (int i = mid + 1; i <= r; ++i){
        if (!open[a[i]]){
            open[a[i]] = 1;
            last = Query(a[i]);
        }
    }
    vector <int> left, right;
    int _ = 0;
    for (_ = 0; _ < w.size(); ++_){
        int i = w[_];
        int tem = Query(i);
        ++cntt;
        open[i] ^= 1;
        if (last == tem) left.pb(i);
        else right.pb(i);
        if (left.size() == r - mid || right.size() == mid - l + 1) break;
        last = tem;
    }
    ++_;
    if (left.size() == r - mid){
        for (; _ < w.size(); ++_){
            int i = w[_];
            right.pb(i);
        }
    }
    else if (right.size() == mid - l + 1){
        for (; _ < w.size(); ++_){
            int i = w[_];
            left.pb(i);
        }
    }
    swap(left, right);
    //cerr << l << " " << r << " " << mid << " " << left.size() << " " << right.size() << "\n";
    assert(right.size() == r - mid);
    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);
}

Compilation message (stderr)

minerals.cpp: In function 'void parallel_bs(std::vector<int>&, int, int)':
minerals.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (_ = 0; _ < w.size(); ++_){
      |                 ~~^~~~~~~~~~
minerals.cpp:66:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |         if (left.size() == r - mid || right.size() == mid - l + 1) break;
      |             ~~~~~~~~~~~~^~~~~~~~~~
minerals.cpp:66:52: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |         if (left.size() == r - mid || right.size() == mid - l + 1) break;
      |                                       ~~~~~~~~~~~~~^~~~~~~~~~~~~~
minerals.cpp:70:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   70 |     if (left.size() == r - mid){
      |         ~~~~~~~~~~~~^~~~~~~~~~
minerals.cpp:71:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (; _ < w.size(); ++_){
      |                ~~^~~~~~~~~~
minerals.cpp:76:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |     else if (right.size() == mid - l + 1){
      |              ~~~~~~~~~~~~~^~~~~~~~~~~~~~
minerals.cpp:77:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         for (; _ < w.size(); ++_){
      |                ~~^~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from minerals.cpp:1:
minerals.cpp:84:25: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |     assert(right.size() == r - mid);
      |            ~~~~~~~~~~~~~^~~~~~~~~~

• 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