Submission #487300

#	Time	Username	Problem	Language	Result	Execution time	Memory
487300		Rainbowbunny	Minerals (JOI19_minerals)	C++17	100 / 100	49 ms	3272 KiB

minerals

#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 45005;

bool In[2 * MAXN];
int lst = 0;
bool query(int i) {
    In[i] ^= 1;
    int cur = Query(i);
    bool ans = cur != lst;
    return lst = cur, ans;
}

int idx[2 * MAXN];
vector<int> A, B;
vector<pair<int, int>> pairs;

constexpr double rat = 1 / 2.56; //ternary
void dfs(int l, int r, const vector<int>& b, bool is_on) {
    if(l == r) {
        assert(b.size() == 1);
        pairs.emplace_back(idx[A[l]], idx[b[0]]);
        return;
    }
    int m = l + (r - l) * rat;
    for(int i = l; i <= m; i++) query(idx[A[i]]);
    vector<int> lf, rg;
    for(int id: b) {
        if(lf.size() == m - l + 1) rg.push_back(id);
        else if(rg.size() == r - m) lf.push_back(id);
        else (query(idx[id]) == is_on ? lf : rg).push_back(id);
    }
    dfs(l, m, lf, is_on ^ 1);
    if(m < r) dfs(m + 1, r, rg, is_on);
} 

void Solve(int n) {
    mt19937 rng(233);
    iota(idx + 1, idx + (2 * n) + 1, 1);
    shuffle(idx + 1, idx + (2 * n) + 1, rng);
    for(int i = 1; i <= 2 * n; i++) (query(idx[i]) ? A : B).push_back(i);
    dfs(0, n - 1, B, 1);
    assert(pairs.size() == n);
    for(auto& x: pairs) Answer(x.first, x.second);
}

Compilation message (stderr)

minerals.cpp: In function 'void dfs(int, int, const std::vector<int>&, bool)':
minerals.cpp:31:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |         if(lf.size() == m - l + 1) rg.push_back(id);
      |            ~~~~~~~~~~^~~~~~~~~~~~
minerals.cpp:32:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         else if(rg.size() == r - m) lf.push_back(id);
      |                 ~~~~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from minerals.cpp:2:
minerals.cpp: In function 'void Solve(int)':
minerals.cpp:45:25: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |     assert(pairs.size() == n);
      |            ~~~~~~~~~~~~~^~~~

• 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