Submission #916288

#	Time	Username	Problem	Language	Result	Execution time	Memory
916288		boris_mihov	Minerals (JOI19_minerals)	C++17	40 / 100	88 ms	59840 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;
struct Material
{
    int idx;
    int l, r;
};

int perm[MAXN];
bool isIn[MAXN];
std::vector <int> unique;
std::vector <int> second;
std::vector <int> secondCopy;
std::deque <Material> waitlist[MAXN];
std::mt19937 rng(123456789);

int countDiff;
int query(int idx)
{
    // std::cout << "call query: " << idx << '\n';
    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);

    unique.push_back(0);
    second.push_back(0);
    int last = 0;

    for (int i = 1 ; i <= 2 * n ; ++i)
    {
        if (unique.size() < n + 1 && (second.size() == n + 1 || query(i) > last))
        {
            last++;
            unique.push_back(i);
        } else
        {
            // std::cout << "push: " << i << ' ' << 1 << ' ' << (int)unique.size() - 1 << '\n';
            waitlist[1].push_back({i, 1, (int)unique.size() - 1});
            second.push_back(i);
        }
    }

    // std::cout << "unique\n";
    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     std::cout << unique[i] << ' ';
    // }

    // std::cout << '\n';

    assert(unique.size() == n + 1);
    assert(second.size() == n + 1);
    secondCopy.resize(n + 1);

    int ptr = n;
    for (int level = 1 ; waitlist[level].size() ; ++level)
    {
        // std::cout << " new level: " << level << '\n';
        if (level & 1)
        {
            std::sort(waitlist[level].begin(), waitlist[level].end(), [&](auto x, auto y)
            {
                return x.l + x.r > y.l + y.r;
            });
        } else
        {
            std::sort(waitlist[level].begin(), waitlist[level].end(), [&](auto x, auto y)
            {
                return x.l + x.r < y.l + y.r;
            });
        }

        bool wasIn = false;
        while (waitlist[level].size())
        {
            auto [idx, l, r] = waitlist[level].front();
            waitlist[level].pop_front();

            // std::cout << "here: " << idx << ' ' << l << ' ' << r << '\n';
            if (l == r)
            {
                answer(unique[l], idx);
                continue;
            }

            int mid = (l + r) / 2;
            if (!wasIn)
            {
                if (level & 1)
                {
                    while (ptr < mid)
                    {
                        ptr++;
                        query(unique[ptr]);
                    }
                } else
                {
                    while (ptr > mid)
                    {
                        query(unique[ptr]);
                        ptr--;
                    }
                }

                wasIn = true;
            }

            if (level % 2 == 0)
            {
                while (ptr < mid)
                {
                    ptr++;
                    query(unique[ptr]);
                }
            } else
            {
                while (ptr > mid)
                {
                    query(unique[ptr]);
                    ptr--;
                }
            }

            int last = countDiff;
            query(idx);

            if (last == countDiff)
            {
                waitlist[level + 1].push_back({idx, l, mid});
            } else
            {
                waitlist[level + 1].push_back({idx, mid + 1, r});
            }
        }
    }
}

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:54:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         if (unique.size() < n + 1 && (second.size() == n + 1 || query(i) > last))
      |             ~~~~~~~~~~~~~~^~~~~~~
minerals.cpp:54:53: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         if (unique.size() < n + 1 && (second.size() == n + 1 || query(i) > last))
      |                                       ~~~~~~~~~~~~~~^~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from minerals.cpp:5:
minerals.cpp:74:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   74 |     assert(unique.size() == n + 1);
      |            ~~~~~~~~~~~~~~^~~~~~~~
minerals.cpp:75:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |     assert(second.size() == n + 1);
      |            ~~~~~~~~~~~~~~^~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 0 / 30
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 10