Submission #771981

#	Time	Username	Problem	Language	Result	Execution time	Memory
771981		doowey	Minerals (JOI19_minerals)	C++14	90 / 100	317 ms	8120 KiB

minerals

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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#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)]);
    }
}

const ld golden = 0.4;

int split(int sz){
    return (int)ceil((ld)sz * golden);
}

void pair_up(vector<int> A, vector<int> B, bool in_a, bool in_b){
    if(A.empty()) return;
    if(A.size() == 1){
        ans.push_back(mp(A[0], B[0]));
        return;
    }
    shuffle(A);
    shuffle(B);
    int mid = split(A.size());
    vector<int> a0, a1;
    bool ia0 = in_a, ia1 = in_a;
    bool ib0 = in_b, ib1 = in_b;
    vector<int> b0, b1;
    for(int i = 0 ; i < mid; i ++ ){
        int cur = ask(A[i]);
        las=cur;
        a0.push_back(A[i]);
    }
    ia0 ^= 1;
    for(int i = mid ; i < A.size(); i ++ ){
        a1.push_back(A[i]);
    }
    ib0 ^= 1;
    for(auto x : B){
        if(A.size() <= 4){
            if(b0.size() == a0.size()){
                b1.push_back(x);
                continue;
            }
            else if(b1.size() == a1.size()){
                b0.push_back(x);
                continue;
            }

        }
        int cur = ask(x);
        if(cur == las){
            if(ia0) b0.push_back(x);
            else b1.push_back(x);
        }
        else{
            if(ia0) b1.push_back(x);
            else b0.push_back(x);
        }
        las = cur;
    }
    pair_up(a0, b0, ia0, ib0);
    pair_up(a1, b1, ia1, ib1);
}


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, true);
    for (auto x : ans)
        Answer(x.fi, x.se);
}

Compilation message (stderr)

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