Submission #771945

#	Time	Username	Problem	Language	Result	Execution time	Memory
771945		doowey	Minerals (JOI19_minerals)	C++17	40 / 100	321 ms	7352 KiB

minerals

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

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

int gen(int m){
    return ((int)rng() % m + m) % m;
}

int las;
vector<pii> ans;
set<int> E;

int ask(int id){
    if(E.count(id)) E.erase(id);
    else E.insert(id);

    int res = Query(id);
    return res;
}

void shuffle(vector<int> &ord){
    for(int i = 0 ; i < ord.size(); i ++ ){
        swap(ord[i], ord[gen(i + 1)]);
    }
}


void pair_up(vector<int> A, vector<int> B, bool inq){
    if(A.empty()) return;
    if(A.size() == 1){
        ans.push_back(mp(A[0], B[0]));
        return;
    }
    shuffle(A);
    shuffle(B);
    int mid = (int)A.size() / 2;
    vector<int> a0, a1;
    vector<int> b0, b1;
    for(int i = 0 ; i < mid; i ++ ){
        int cur = ask(A[i]);
        las=cur;
        a0.push_back(A[i]);
    }
    for(int i = mid ; i < A.size(); i ++ ){
        a1.push_back(A[i]);
    }
    int cnt = 0;
    vector<int> take_out;
    for(auto x : B){
        if(!inq){
            if(b0.size() == a0.size()) {
                b1.push_back(x);
                continue;
            }
        }
        else{
            if(b0.size() == a1.size()){
                b1.push_back(x);
                continue;
            }
        }
        int cur = ask(x);
        if(cur == las){
            b0.push_back(x);
            cnt ++ ;
        }
        else{
            b1.push_back(x);
            take_out.push_back(x);
        }
        las=cur;
    }
    for(auto x : take_out){
        int cur = ask(x);
        las = cur;
    }
    if(inq)
        swap(b0,b1);
    pair_up(a0, b0, (inq ^ 1));
    pair_up(a1, b1, inq);
}


void Solve(int n) {
    las = 0;
    ans.clear();
    vector<int> ord;
    for(int i = 1; i <= 2 * n; i ++ ){
        ord.push_back(i);
    }
    shuffle(ord);
    vector<int> aa, bb;
    for(auto x : ord){
        int cur = ask(x);
        if(cur != las){
            aa.push_back(x);
        }
        else{
            bb.push_back(x);
        }
        las = cur;
    }
    pair_up(aa, bb, true);
    for (auto x : ans)
        Answer(x.fi, x.se);
}

Compilation message (stderr)

minerals.cpp: In function 'void shuffle(std::vector<int>&)':
minerals.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0 ; i < ord.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
minerals.cpp: In function 'void pair_up(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:54:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = mid ; i < A.size(); i ++ ){
      |                       ~~^~~~~~~~~~

• 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