Submission #922891

#	Time	Username	Problem	Language	Result	Execution time	Memory
922891		boris_mihov	Minerals (JOI19_minerals)	C++17	85 / 100	38 ms	5208 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(76543);
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;
    for (int bit = lg ; bit >= 0 ; --bit)
    {
        // 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(min, min + n, INF);
        for (int i = 0 ; i < n ; ++i)
        {
            // std::cout << "prefix: " << i << ' ' << (maskFound & i) << '\n';
            taken[(i >> bit + 1) << bit + 1]++;
            taken2[(i >> bit + 1) << bit + 1]++;
            if (i & (1 << bit)) taken1[(i >> bit + 1) << bit + 1]++;
            else taken0[(i >> bit + 1) << bit + 1]++;

            if (((i & (1 << bit)) > 0) != isIn[unique[i]])
            {
                query(unique[i]);
            }

            if (isIn[unique[i]])
            {
                min[(i >> bit + 1) << bit + 1] = std::min(min[(i >> bit + 1) << bit + 1], i);
            }
        }

        // std::cout << "zero: " << taken[0] << ' ' << n << '\n';
        for (int i = 0 ; i < n ; ++i)
        {
            taken[with[second[i]]]--;
            if (to[second[i]] < min[with[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:80:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |             taken[(i >> bit + 1) << bit + 1]++;
      |                         ~~~~^~~
minerals.cpp:80:41: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   80 |             taken[(i >> bit + 1) << bit + 1]++;
      |                                     ~~~~^~~
minerals.cpp:81:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   81 |             taken2[(i >> bit + 1) << bit + 1]++;
      |                          ~~~~^~~
minerals.cpp:81:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   81 |             taken2[(i >> bit + 1) << bit + 1]++;
      |                                      ~~~~^~~
minerals.cpp:82:50: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |             if (i & (1 << bit)) taken1[(i >> bit + 1) << bit + 1]++;
      |                                              ~~~~^~~
minerals.cpp:82:62: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   82 |             if (i & (1 << bit)) taken1[(i >> bit + 1) << bit + 1]++;
      |                                                          ~~~~^~~
minerals.cpp:83:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |             else taken0[(i >> bit + 1) << bit + 1]++;
      |                               ~~~~^~~
minerals.cpp:83:47: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   83 |             else taken0[(i >> bit + 1) << bit + 1]++;
      |                                           ~~~~^~~
minerals.cpp:92:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |                 min[(i >> bit + 1) << bit + 1] = std::min(min[(i >> bit + 1) << bit + 1], i);
      |                           ~~~~^~~
minerals.cpp:92:43: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   92 |                 min[(i >> bit + 1) << bit + 1] = std::min(min[(i >> bit + 1) << bit + 1], i);
      |                                       ~~~~^~~
minerals.cpp:92:73: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |                 min[(i >> bit + 1) << bit + 1] = std::min(min[(i >> bit + 1) << bit + 1], i);
      |                                                                     ~~~~^~~
minerals.cpp:92:85: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   92 |                 min[(i >> bit + 1) << bit + 1] = std::min(min[(i >> bit + 1) << bit + 1], i);
      |                                                                                 ~~~~^~~
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: 0 / 5
• Subtask 9: 0 / 10