Submission #922871

#	Time	Username	Problem	Language	Result	Execution time	Memory
922871		boris_mihov	Minerals (JOI19_minerals)	C++17	75 / 100	31 ms	4172 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];
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;
        
        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 (bit == 0 && taken[with[second[i]]])
            {
                if (taken[with[second[i]]] == 1)
                {
                    with[second[i]] |= (1 << bit);
                }

                continue;
            }
            
            int curr = countDiff;
            int next = query(second[i]);
            if (curr == next)
            {
                if (bit == 0) taken[with[second[i]]] = 2;
                with[second[i]] |= (1 << bit);
                cntIn--;
            } else
            {
                if (bit == 0) taken[with[second[i]]] = 1;
                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:46:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         if (unique.size() < n && (second.size() == n || query(i) > last))
      |             ~~~~~~~~~~~~~~^~~
minerals.cpp:46:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         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:56:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     assert(unique.size() == n);
      |            ~~~~~~~~~~~~~~^~~~
minerals.cpp:57:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |     assert(second.size() == n);
      |            ~~~~~~~~~~~~~~^~~~
minerals.cpp:60:21: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   60 |     while ((1 << lg + 1) < n)
      |                  ~~~^~~
minerals.cpp:42:9: warning: unused variable 'cnt' [-Wunused-variable]
   42 |     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: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10