제출 #1163969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163969		Shadow1	Minerals (JOI19_minerals)	C++20	40 / 100	84 ms	4264 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using str = string; // yay python!

#define show(x) cerr << (#x) << " = " << (x) << '\n';
#define output_vector(v) for(auto &x : v){cout << x << ' ';}cout << '\n';
#define output_pairvector(v) for(auto &x : v){cout << x.first << " " << x.second << '\n';}
#define read_vector(v) for(auto &x : v){cin >> x;}
#define vt vector
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define pii pair<int,int>
#define fir first
#define sec second
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());

const int maxn = 1e5;
set<int> machine;

void dnc(vector<int> a, vector<int> b) {
    int n = sz(a); // 2N
    if(n == 1) {
        // show(a[0]);
        // show(b[0]);
        Answer(a[0], b[0]);
        return;
    }
    vector<int> a1, b1, a2, b2;
    int cnt = 0;
    for(auto &A : a)
        cnt += (machine.count(A));
    for(int i=0; i<n; ++i) {
        if(cnt < n/2) {
            if(!machine.count(a[i])) { // not in machine, add the left part
                Query(a[i]);    
                machine.insert(a[i]);
                ++cnt;
            } 
            a1.push_back(a[i]);
        } else if(cnt > n/2) {
            if(machine.count(a[i])) { // not in machine, add the left part
                Query(a[i]);    
                machine.erase(a[i]);
                --cnt;
            } 
            a2.push_back(a[i]);
        } else {
            if(machine.count(a[i]))
                a1.push_back(a[i]);
            else
                a2.push_back(a[i]);
        }
    }
    Query(1);
    int d = Query(1);

    for(auto &B : b) {
        // if(sz(b1) == n/2) {
        //     b2.push_back(B);
        //     continue;
        // }
        // if(sz(b2) == n/2) {
        //     b1.push_back(B);
        //     continue;
        // }
        int res = Query(B);
        if(!machine.count(B)) {
            if(d != res) 
                b1.push_back(B);
            else 
                b2.push_back(B);
        } else {
            if(d != res) 
                b2.push_back(B);
            else 
                b1.push_back(B);
        }
        d = res;
    }           
    dnc(a1, b1);
    dnc(a2, b2);

}

void Solve(int N) {
    vector<int> x, y;
    int d = 0;
    for(int i=1; i<=2*N; ++i) {
        int res = Query(i);
        if(res > d)
            x.push_back(i);
        else
            y.push_back(i);
        d = res;
    }
    // for(auto &k : machine)
    //     Query(k);
    // machine.clear();
    dnc(x, y);
}

• 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