Submission #623557

#	Time	Username	Problem	Language	Result	Execution time	Memory
623557		AlperenT	Minerals (JOI19_minerals)	C++17	100 / 100	473 ms	13256 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"
 
using namespace std;
 
const int N = 50000 + 5;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int n, ans[N], ptr, cnt, test;
 
set<int> cur;
 
int query(int x){
    if(cur.find(x) != cur.end()) cur.erase(x);
    else cur.insert(x);
 
    return cnt = Query(x);
}
 
vector<int> treevec;
 
struct SegTree{
    map<int, vector<pair<int, int>>> tree;
 
    void clear(){
        tree.clear();
    }
 
    void build(int v, int l, int r, bool flag){
        if(l > r) return;
 
        if(l == r) ans[l] = tree[v].front().second;
        else{
            // int m = l + (r - l) * 0.385;

            int m = l + (r - l) * 0.37;
 
            for(int i = l; i <= m; i++) query(treevec[i]);

            // sort(tree[v].begin(), tree[v].end());

            shuffle(tree[v].begin(), tree[v].end(), rng);
 
            for(auto p : tree[v]){
                if(p.first <= m){
                    tree[v * 2].push_back(p);
                    test++;
                }
                else if(tree[v * 2].size() == (m - l + 1)) tree[v * 2 + 1].push_back(p);
                else if(tree[v * 2 + 1].size() == (r - (m + 1) + 1)) tree[v * 2].push_back(p);
                else{
                    if(cur.find(p.second) == cur.end()){
                        int prevcnt = cnt;
 
                        query(p.second);
 
                        if(prevcnt + 1 == cnt) tree[v * 2 + flag].push_back(p);
                        else tree[v * 2 + !flag].push_back(p);
                    }
                    else{
                        int prevcnt = cnt;
 
                        query(p.second);
 
                        if(prevcnt == cnt) tree[v * 2 + !flag].push_back(p);
                        else tree[v * 2 + flag].push_back(p);
                    }
                }
            }
 
            build(v * 2, l, m, !flag);
            build(v * 2 + 1, m + 1, r, flag);
        }
    }
};
 
SegTree sgt;

void match(vector<int> a, vector<pair<int, int>> b){
    treevec = a;
 
    sgt.clear();
 
    for(auto p : b) sgt.tree[1].push_back(p);
 
    sgt.build(1, 0, (int)a.size() - 1, true);
 
    for(int i = 0; i < a.size(); i++) Answer(treevec[i], ans[i]);
}
 
void Solve(int N_) {
    n = N_;
 
    vector<int> v(n * 2);
 
    iota(v.begin(), v.end(), 1);

    shuffle(v.begin(), v.end(), rng);

    vector<int> a, c1, c2, indexes;
    vector<pair<int, int>> tmp, b;
 
    for(int i = 0; i < n; i++){
        int prevcnt = cnt;

        query(v[i]);

        if(cnt == prevcnt + 1) tmp.push_back({i, v[i]});
        else b.push_back({i, v[i]});
    }

    reverse(tmp.begin(), tmp.end());

    while(!tmp.empty()){
        pair<int, int> p = tmp.back();
        tmp.pop_back();

        int prevcnt = cnt;

        query(p.second);

        if(cnt == prevcnt - 1) c1.push_back(p.second);
        else{
            a.push_back(p.second);
            indexes.push_back(p.first);
        }
    }

    for(auto &p : b) p.first = upper_bound(indexes.begin(), indexes.end(), p.first) - indexes.begin() - 1;

    match(a, b);

    a.clear(), b.clear(), tmp.clear(), indexes.clear();

    for(int i = n; i < n * 2; i++){
        int prevcnt = cnt;

        query(v[i]);

        if(cnt == prevcnt + 1) tmp.push_back({i, v[i]});
        else b.push_back({i, v[i]});
    }

    reverse(tmp.begin(), tmp.end());

    while(!tmp.empty()){
        pair<int, int> p = tmp.back();
        tmp.pop_back();

        int prevcnt = cnt;

        query(p.second);

        if(cnt == prevcnt - 1) c2.push_back(p.second);
        else{
            a.push_back(p.second);
            indexes.push_back(p.first);
        }
    }

    for(auto &p : b) p.first = upper_bound(indexes.begin(), indexes.end(), p.first) - indexes.begin() - 1;

    match(a, b);

    a = c1;

    b.clear();

    for(auto x : c2) b.push_back({a.size(), x});

    match(a, b);
}

Compilation message (stderr)

minerals.cpp: In member function 'void SegTree::build(int, int, int, bool)':
minerals.cpp:50:44: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |                 else if(tree[v * 2].size() == (m - l + 1)) tree[v * 2 + 1].push_back(p);
      |                         ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
minerals.cpp:51:48: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |                 else if(tree[v * 2 + 1].size() == (r - (m + 1) + 1)) tree[v * 2].push_back(p);
      |                         ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
minerals.cpp: In function 'void match(std::vector<int>, std::vector<std::pair<int, int> >)':
minerals.cpp:89:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i = 0; i < a.size(); i++) Answer(treevec[i], ans[i]);
      |                    ~~^~~~~~~~~~

• 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: 10 / 10