Submission #973160

#	Time	Username	Problem	Language	Result	Execution time	Memory
973160		the_coding_pooh	Minerals (JOI19_minerals)	C++14	100 / 100	42 ms	4516 KiB

minerals

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

// #define __LOCAL__

#ifdef __LOCAL__
void Solve(int N);

const int SIZE = 1e3 + 5;

int type[SIZE], cnt[SIZE], in_cnt[SIZE];

int ttl = 0, qcnt = 0;

int Query(int i){
    qcnt++;
    if(!cnt[type[i]])
        ttl++;
    if(in_cnt[i]){
        cnt[type[i]]--;
        in_cnt[i] = 0;
    }
    else if(!in_cnt[i]){
        cnt[type[i]]++;
        in_cnt[i] = 1;
    }
    if(!cnt[type[i]])
        ttl--;

    return ttl;
}

void Answer(int a, int b){
    if(type[a] != type[b])
        cout << a << ' ' << b << " WA\n";
}

int main(){
    int n;
    cin >> n;
    for (int i = 1, a, b; i <= n;i++){
        cin >> a >> b;
        type[a] = i;
        type[b] = i;
    }
    Solve(n);
    cout << qcnt << '\n';

}
#endif
#ifndef __LOCAL__
#include "minerals.h"
#endif

#define uwu return;

const double magic = exp(-1);

void solve(vector<int> A, vector<int> B, bool b){
    if(A.empty())
        uwu
    if(A.size() == 1){
        Answer(A[0], B[0]);
        uwu
    }
    
    int m = max((int) (b * A.size() + (1 - b * 2) * magic * A.size()), 1);

    vector<int> recA[2], recB[2];

    for (int i = 0; i < A.size(); i++){
        recA[i >= m].push_back(A[i]);
    }

    int prev;

    for(auto i : recA[b]){
        prev = Query(i);
    }

    for(auto i : B){
        if(recA[0].size() == recB[0].size()){
            recB[1].push_back(i);
        }
        else if(recA[1].size() == recB[1].size()){
            recB[0].push_back(i);
        }
        else{
            int now = Query(i);
            now == prev ? recB[0].push_back(i) : recB[1].push_back(i);
            prev = now;
        }
    }

    solve(recA[0], recB[0], 1), solve(recA[1], recB[1], 0);
    return;
}

void Solve(int N){
    vector<int> veca, vecb;

    for (int i = 1, pre = 0, tmp = 0; i <= 2 * N; i++){
        tmp = Query(i);
        if(tmp == pre)
            veca.push_back(i);
        else
            vecb.push_back(i);
        pre = tmp;
    }

    random_shuffle(veca.begin(), veca.end());
    random_shuffle(vecb.begin(), vecb.end());

    solve(veca, vecb, 1);
    uwu
}

Compilation message (stderr)

minerals.cpp: In function 'void solve(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < A.size(); i++){
      |                     ~~^~~~~~~~~~
minerals.cpp:90:25: warning: 'prev' may be used uninitialized in this function [-Wmaybe-uninitialized]
   90 |             now == prev ? recB[0].push_back(i) : recB[1].push_back(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: 10 / 10