Submission #637392

#	Time	Username	Problem	Language	Result	Execution time	Memory
637392		AlperenT	Minerals (JOI19_minerals)	C++17	100 / 100	389 ms	6444 KiB

minerals

#include <bits/stdc++.h>
#include "minerals.h"

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int cnt;

set<int> minerals;

int query(int x){
    if(minerals.find(x) != minerals.end()) minerals.erase(x);
    else minerals.insert(x);

    return cnt = Query(x);
}

struct Item{
    int x, i;
};

void solve(int l, int r, vector<int> &a, vector<Item> b, bool flag){
    if(l > r) return;
    else if(l == r) Answer(a[l], b[0].x);
    else{
        int m = r - (r - l) * 0.375;

        vector<Item> lft, rght;

        for(int i = m + 1; i <= r; i++) query(a[i]);

        for(auto p : b){
            if(p.i <= m) lft.push_back(p);
            else if(lft.size() == m - l + 1) rght.push_back(p);
            else if(rght.size() == r - m) lft.push_back(p);
            else if(minerals.find(p.x) == minerals.end()){
                int prvcnt = cnt;

                query(p.x);

                if(flag){
                    if(cnt == prvcnt + 1) rght.push_back(p);
                    else lft.push_back(p);
                }
                else{
                    if(cnt == prvcnt + 1) lft.push_back(p);
                    else rght.push_back(p);
                }
            }
            else{
                int prvcnt = cnt;

                query(p.x);

                if(flag){
                    if(cnt == prvcnt - 1) rght.push_back(p);
                    else lft.push_back(p);
                }
                else{
                    if(cnt == prvcnt - 1) lft.push_back(p);
                    else rght.push_back(p);
                }
            }
        }

        solve(l, m, a, lft, flag);
        solve(m + 1, r, a, rght, !flag);
    }
}

void Solve(int n) {
    vector<int> nums, a, c1, c2, indxs;
    vector<Item> tmp, b;

    nums.assign(n * 2, 0);
    iota(nums.begin(), nums.end(), 1);

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

    for(int i = 0; i < n; i++){
        int prvcnt = cnt;

        query(nums[i]);

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

    for(auto p : tmp){
        int prvcnt = cnt;

        query(p.x);

        if(cnt == prvcnt - 1) c1.push_back(p.x);
        else{
            a.push_back(p.x);
            indxs.push_back(p.i);
        }
    }

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

    solve(0, (int)a.size() - 1, a, b, false);

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

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

        query(nums[i]);

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

    for(auto p : tmp){
        int prvcnt = cnt;

        query(p.x);

        if(cnt == prvcnt - 1) c2.push_back(p.x);
        else{
            a.push_back(p.x);
            indxs.push_back(p.i);
        }
    }

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

    solve(0, (int)a.size() - 1, a, b, false);

    a = c1;

    b.clear();

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

    solve(0, (int)a.size() - 1, a, b, false);
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(int, int, std::vector<int>&, std::vector<Item>, bool)':
minerals.cpp:35:32: warning: comparison of integer expressions of different signedness: 'std::vector<Item>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |             else if(lft.size() == m - l + 1) rght.push_back(p);
      |                     ~~~~~~~~~~~^~~~~~~~~~~~
minerals.cpp:36:33: warning: comparison of integer expressions of different signedness: 'std::vector<Item>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |             else if(rght.size() == r - m) lft.push_back(p);
      |                     ~~~~~~~~~~~~^~~~~~~~

• 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