Submission #922875

#	Time	Username	Problem	Language	Result	Execution time	Memory
922875		boris_mihov	Minerals (JOI19_minerals)	C++17	80 / 100	38 ms	4340 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 with[MAXN];
int perm[MAXN];
bool isIn[MAXN];
int taken[MAXN];
int taken0[MAXN];
int taken1[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++;
    }

    for (int bit = lg ; bit >= 0 ; --bit)
    {
        int cntIn = 0;
        int cntOut = 0;
        int min = INF;
        
        std::fill(taken, taken + n, 0);
        std::fill(taken0, taken0 + n, 0);
        std::fill(taken1, taken1 + n, 0);
        for (int i = 0 ; i < n ; ++i)
        {
            if (((i & (1 << bit)) > 0) != isIn[unique[i]])
            {
                query(unique[i]);
            }

            if (isIn[unique[i]])
            {
                min = std::min(min, i);
            }

            cntIn += isIn[unique[i]];
            cntOut += !isIn[unique[i]];
        }

        for (int i = 0 ; i < n ; ++i)
        {
            if (cntIn == 0)
            {
                continue;
            }

            if (to[second[i]] < min)
            {
                cntOut--;
                continue;
            }

            if (cntOut == 0)
            {
                with[second[i]] |= (1 << bit);
                continue;
            }

            if (taken[with[second[i]]] == (1 << bit + 1) - 1)
            {
                if (taken1[with[second[i]]] < taken0[with[second[i]]])
                {
                    with[second[i]] |= (1 << bit);
                }

                continue;
            }
            
            int curr = countDiff;
            int next = query(second[i]);
            taken[with[second[i]]]++;
            if (curr == next)
            {
                taken1[with[second[i]]]++;
                with[second[i]] |= (1 << bit);
                cntIn--;
            } else
            {
                taken0[with[second[i]]]++;
                cntOut--;
            }
        }
    }

    for (int i = 0 ; i < n ; ++i)
    {
        answer(second[i], unique[with[second[i]]]);
    }
}

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:48:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         if (unique.size() < n && (second.size() == n || query(i) > last))
      |             ~~~~~~~~~~~~~~^~~
minerals.cpp:48:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |         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:58:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   58 |     assert(unique.size() == n);
      |            ~~~~~~~~~~~~~~^~~~
minerals.cpp:59:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |     assert(second.size() == n);
      |            ~~~~~~~~~~~~~~^~~~
minerals.cpp:62:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   62 |     while ((1 << lg + 1) < n)
      |                  ~~~^~~
minerals.cpp:111:53: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
  111 |             if (taken[with[second[i]]] == (1 << bit + 1) - 1)
      |                                                 ~~~~^~~
minerals.cpp:44:9: warning: unused variable 'cnt' [-Wunused-variable]
   44 |     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: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10