Submission #623207

#	Time	Username	Problem	Language	Result	Execution time	Memory
623207		Be_dos	Minerals (JOI19_minerals)	C++17	100 / 100	70 ms	3420 KiB

minerals

#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>

//#define LOCAL
#ifndef LOCAL
#include "minerals.h"
#endif
#ifdef LOCAL

int32_t* arr;

std::map<int32_t, int32_t> kinds_cur;
int32_t ans_cur;
bool* taken_cur;
int32_t query_cnt = 0;
int32_t Query(int32_t ind) {
    ind--;
    query_cnt++;
    if(taken_cur[ind]) {
        kinds_cur[arr[ind]]--;
        if(kinds_cur[arr[ind]] == 0)
            ans_cur--;
    } else {
        kinds_cur[arr[ind]]++;
        if(kinds_cur[arr[ind]] == 1)
            ans_cur++;
    }
    taken_cur[ind] = !taken_cur[ind];
    return ans_cur;
}

std::vector<std::pair<int32_t, int32_t> > ans_vec;
void Answer(int32_t a, int32_t b) {
    a--;
    b--;
    ans_vec.emplace_back(a, b);
}

#endif

int32_t* perm;
bool* taken_cur2;
int32_t last_q;
int32_t query(int32_t ind) {
    taken_cur2[ind] = !taken_cur2[ind];
    last_q = Query(perm[ind] + 1);
    return last_q;
}

void answer(int32_t a, int32_t b) {
    Answer(perm[a] + 1, perm[b] + 1);
}

void rec_solve(std::vector<int32_t>& lefts, std::vector<int32_t>& rights) {
    if(lefts.size() == 1) {
        answer(lefts[0], rights[0]);
        return;
    }

    int32_t cnt_left = 0;
    int32_t cnt_right = 0;
    for(int32_t i = 0; i < lefts.size(); i++) {
        if(taken_cur2[lefts[i]])
            cnt_left++;
        if(taken_cur2[rights[i]])
            cnt_right++;
    }
    int32_t steps_left = std::min(std::abs((int32_t)lefts.size() / 2 - cnt_left), std::abs((int32_t)(lefts.size() + 1) / 2 - cnt_left));
    int32_t steps_right = std::min(std::abs((int32_t)rights.size() / 2 - cnt_right), std::abs((int32_t)(rights.size() + 1) / 2 - cnt_right));
    if(steps_left > steps_right)
        std::swap(lefts, rights);

    std::vector<int32_t> lefts1, lefts2;
    for(int32_t i = 0; i < lefts.size(); i++)
        if(taken_cur2[lefts[i]])
            lefts1.push_back(lefts[i]);
        else
            lefts2.push_back(lefts[i]);
    while((int32_t)lefts1.size() - (int32_t)lefts2.size() > 1) {
        query(lefts1.back());
        lefts2.push_back(lefts1.back());
        lefts1.pop_back();
    }
    while((int32_t)lefts2.size() - (int32_t)lefts1.size() > 1) {
        query(lefts2.back());
        lefts1.push_back(lefts2.back());
        lefts2.pop_back();
    }
    std::sort(lefts1.begin(), lefts1.end());
    std::sort(lefts2.begin(), lefts2.end());

    std::vector<int32_t> rights1, rights2;
    int32_t last = last_q;
    for(int32_t i = 0; i < rights.size(); i++) {
        int32_t new_ = query(rights[i]);
        if(new_ != last)
            rights2.push_back(rights[i]);
        else
            rights1.push_back(rights[i]);
        last = new_;

        if(rights1.size() == lefts1.size()) {
            for(int32_t j = i + 1; j < rights.size(); j++)
                rights2.push_back(rights[j]);
            break;
        }
        if(rights2.size() == lefts2.size()) {
            for(int32_t j = i + 1; j < rights.size(); j++)
                rights1.push_back(rights[j]);
            break;
        }
    }

    rec_solve(lefts1, rights1);
    rec_solve(lefts2, rights2);
}

void Solve(int32_t n) {
    std::mt19937 rng2(12345);
    perm = new int32_t[2 * n];
    for(int32_t i = 0; i < 2 * n; i++)
        perm[i] = i;
    taken_cur2 = new bool[2 * n];
    for (int32_t i = 0; i < 2 * n; i++)
        taken_cur2[i] = false;
    std::shuffle(perm, perm + 2 * n, rng2);

    std::vector<int32_t> lefts, rights;
    int32_t last = 0;
    for(int32_t i = 0; i < 2 * n; i++) {
        int32_t new_ = query(i);
        if(new_ != last)
            lefts.push_back(i);
        else
            rights.push_back(i);
        last = new_;
    }

    rec_solve(lefts, rights);
}

#ifdef LOCAL
int main() {
    int32_t n;
    std::cin >> n;

    std::mt19937 rng;
    for(int32_t t = 0; t < 10; t++) {
        arr = new int32_t[2 * n];
        for (int32_t i = 0; i < 2 * n; i++)
            arr[i] = i / 2;
        std::shuffle(arr, arr + 2 * n, rng);

        taken_cur = new bool[2 * n];
        for (int32_t i = 0; i < 2 * n; i++)
            taken_cur[i] = false;

        ans_vec.clear();
        kinds_cur.clear();
        query_cnt = 0;

        Solve(n);

        if (ans_vec.size() != n) {
            std::cout << "BAD";
            return 0;
        }

        for (auto p: ans_vec)
            if (arr[p.first] != arr[p.second]) {
                std::cout << "BAD" << "\n";
                return 0;
            }
        std::cout << "GOOD, used " << query_cnt << " queries" << "\n";
    }
    return 0;
}
#endif

Compilation message (stderr)

minerals.cpp: In function 'void rec_solve(std::vector<int>&, std::vector<int>&)':
minerals.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     for(int32_t i = 0; i < lefts.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~
minerals.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int32_t i = 0; i < lefts.size(); i++)
      |                        ~~^~~~~~~~~~~~~~
minerals.cpp:113:26: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for(int32_t i = 0; i < rights.size(); i++) {
      |                        ~~^~~~~~~~~~~~~~~
minerals.cpp:122:38: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |             for(int32_t j = i + 1; j < rights.size(); j++)
      |                                    ~~^~~~~~~~~~~~~~~
minerals.cpp:127:38: warning: comparison of integer expressions of different signedness: 'int32_t' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |             for(int32_t j = i + 1; j < rights.size(); j++)
      |                                    ~~^~~~~~~~~~~~~~~

• 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