Submission #922951

#	Time	Username	Problem	Language	Result	Execution time	Memory
922951		boris_mihov	Minerals (JOI19_minerals)	C++17	90 / 100	38 ms	4960 KiB

minerals

#include "minerals.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#include <vector>
#include <queue>
 
typedef long long llong;
const int MAXN = 86000 + 10;
const int INF  = 1e9;
 
int n;
int min[MAXN];
int with[MAXN];
int perm[MAXN];
bool isIn[MAXN];
int taken[MAXN];
int taken0[MAXN];
int taken1[MAXN];
int taken2[MAXN];
std::vector <int> unique;
std::vector <int> second;
std::mt19937 rng(69420);
int to[MAXN];
 
int countDiff;
int query(int idx)
{
    isIn[idx] ^= 1;
    return countDiff = Query(perm[idx]);
}
 
void answer(int a, int b)
{
    Answer(perm[a], perm[b]);
}
 
void Solve(int N) 
{
    n = N;
    std::iota(perm + 1, perm + 1 + 2 * n, 1);
    std::shuffle(perm + 1, perm + 1 + 2 * n, rng);
 
    int cnt = 0;
    for (int i = 1 ; i <= 2 * n ; ++i)
    {
        int last = countDiff;
        if (unique.size() < n && (second.size() == n || query(i) > last))
        {
            unique.push_back(i);
        } else
        {
            to[i] = unique.size();
            second.push_back(i);
        }
    }
 
    assert(unique.size() == n);
    assert(second.size() == n);
 
    int lg = 0;
    while ((1 << lg + 1) < n)
    {
        lg++;
    }
 
    int maskFound = 0;
    std::vector <int> order = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    for (int &bit : order)
    {
        // std::cout << "  new bit: " << bit << '\n';        
        std::fill(taken, taken + n, 0);
        std::fill(taken0, taken0 + n, 0);
        std::fill(taken1, taken1 + n, 0);
        std::fill(taken2, taken2 + n, 0);
        std::fill(min, min + n, INF);

        int cnt = 0;
        for (int i = 0 ; i < n ; ++i)   
        {
            // std::cout << "prefix: " << i << ' ' << (maskFound & i) << '\n';
            taken[i & maskFound]++;
            taken2[i & maskFound]++;
            if (i & (1 << bit)) taken1[i & maskFound]++;
            else taken0[i & maskFound]++;

            if (((i & (1 << bit)) > 0) != isIn[unique[i]])
            {
                if (bit < 15 || cnt >= 1500) query(unique[i]);
                cnt++;
            }
 
            if (((i & (1 << bit)) > 0))
            {
                min[i & maskFound] = std::min(min[i & maskFound], i);
            }
        }
 
        // std::cout << "zero: " << taken[0] << ' ' << n << '\n'; 
        // if (bit == 15) std::reverse(second.begin(), second.end());
        for (int i = 0 ; i < n ; ++i)
        {
            taken[with[second[i]]]--;
            if ((with[second[i]] | (1 << bit)) >= to[second[i]])
            {
                taken0[with[second[i]]]--;
                continue;
            }
 
            if (taken1[with[second[i]]] == 0)
            {
                taken0[with[second[i]]]--;
                continue;
            }
 
            if (taken0[with[second[i]]] == 0)
            {
                with[second[i]] |= (1 << bit);
                taken1[with[second[i]]]--;
                continue;
            }
            
            int curr = countDiff;   
            int next = query(second[i]);
            if (curr == next)
            {
                taken1[with[second[i]]]--;
                with[second[i]] |= (1 << bit);
            } else
            {
                taken0[with[second[i]]]--;
            }
        }
    
        maskFound |= (1 << bit);
    }
 
    for (int i = 0 ; i < n ; ++i)
    {
        // if (!(1 <= unique[with[second[i]]] && unique[with[second[i]]] <= 2 * n))
        // {
        //     std::cout << "the fuck: " << second[i] << ' ' << with[second[i]] << ' ' << unique[with[second[i]]] << '\n';
        // }
        answer(second[i], unique[with[second[i]]]);
    }
}

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:50:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         if (unique.size() < n && (second.size() == n || query(i) > last))
      |             ~~~~~~~~~~~~~~^~~
minerals.cpp:50:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         if (unique.size() < n && (second.size() == n || query(i) > last))
      |                                   ~~~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/10/cassert:44,
                 from minerals.cpp:5:
minerals.cpp:60:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   60 |     assert(unique.size() == n);
      |            ~~~~~~~~~~~~~~^~~~
minerals.cpp:61:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     assert(second.size() == n);
      |            ~~~~~~~~~~~~~~^~~~
minerals.cpp:64:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   64 |     while ((1 << lg + 1) < n)
      |                  ~~~^~~
minerals.cpp:46:9: warning: unused variable 'cnt' [-Wunused-variable]
   46 |     int cnt = 0;
      |         ^~~

• 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