Submission #771903

#	Time	Username	Problem	Language	Result	Execution time	Memory
771903		doowey	Minerals (JOI19_minerals)	C++14	40 / 100	39 ms	3564 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;

int ask(int 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){
    if(A.empty()) return;
    if(A.size() == 1){
        ans.push_back(mp(A[0], B[0]));
        return;
    }
    shuffle(A);
    shuffle(B);
    int mid = 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;
    for(auto x : B){
        if(cnt == mid){
            b1.push_back(x);
        }
        else{
            int cur = ask(x);
            if(cur == las){
                b0.push_back(x);
                cnt ++ ;
            }
            else{
                b1.push_back(x);
            }
            las=cur;
        }
    }
    for(auto x : a0){
        ask(x);
    }
    for(auto x : b0){
        ask(x);
    }
    las = 0;
    pair_up(a0, b0);
    pair_up(a1, b1);
}


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;
    }
    for(auto x : ord){
        int cur = ask(x);
        las = cur;
    }
    pair_up(aa, bb);
    for (auto x : ans)
        Answer(x.fi, x.se);
}

Compilation message (stderr)

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