oj.uz

Submission #916288

# Submission time Handle Problem Language Result Execution time Memory
916288 2024-01-25T15:24:32 Z boris_mihov Minerals (JOI19_minerals) C++17
40 / 100
 88 ms 59840 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58456 KB Output is correct
2 Correct 30 ms 58456 KB Output is correct
3 Correct 30 ms 58456 KB Output is correct
4 Correct 31 ms 58508 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58448 KB Output is correct
2 Correct 33 ms 58456 KB Output is correct
3 Correct 35 ms 58712 KB Output is correct
4 Correct 44 ms 58620 KB Output is correct
5 Correct 52 ms 58876 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58456 KB Output is correct
2 Correct 30 ms 58456 KB Output is correct
3 Correct 30 ms 58456 KB Output is correct
4 Correct 31 ms 58508 KB Output is correct
5 Correct 31 ms 58448 KB Output is correct
6 Correct 33 ms 58456 KB Output is correct
7 Correct 35 ms 58712 KB Output is correct
8 Correct 44 ms 58620 KB Output is correct
9 Correct 52 ms 58876 KB Output is correct
10 Correct 33 ms 58456 KB Output is correct
11 Correct 51 ms 58884 KB Output is correct
12 Correct 56 ms 58968 KB Output is correct
13 Correct 44 ms 59044 KB Output is correct
14 Correct 50 ms 58864 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58456 KB Output is correct
2 Correct 30 ms 58456 KB Output is correct
3 Correct 30 ms 58456 KB Output is correct
4 Correct 31 ms 58508 KB Output is correct
5 Correct 31 ms 58448 KB Output is correct
6 Correct 33 ms 58456 KB Output is correct
7 Correct 35 ms 58712 KB Output is correct
8 Correct 44 ms 58620 KB Output is correct
9 Correct 52 ms 58876 KB Output is correct
10 Correct 33 ms 58456 KB Output is correct
11 Correct 51 ms 58884 KB Output is correct
12 Correct 56 ms 58968 KB Output is correct
13 Correct 44 ms 59044 KB Output is correct
14 Correct 50 ms 58864 KB Output is correct
15 Incorrect 88 ms 59840 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58456 KB Output is correct
2 Correct 30 ms 58456 KB Output is correct
3 Correct 30 ms 58456 KB Output is correct
4 Correct 31 ms 58508 KB Output is correct
5 Correct 31 ms 58448 KB Output is correct
6 Correct 33 ms 58456 KB Output is correct
7 Correct 35 ms 58712 KB Output is correct
8 Correct 44 ms 58620 KB Output is correct
9 Correct 52 ms 58876 KB Output is correct
10 Correct 33 ms 58456 KB Output is correct
11 Correct 51 ms 58884 KB Output is correct
12 Correct 56 ms 58968 KB Output is correct
13 Correct 44 ms 59044 KB Output is correct
14 Correct 50 ms 58864 KB Output is correct
15 Incorrect 88 ms 59840 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58456 KB Output is correct
2 Correct 30 ms 58456 KB Output is correct
3 Correct 30 ms 58456 KB Output is correct
4 Correct 31 ms 58508 KB Output is correct
5 Correct 31 ms 58448 KB Output is correct
6 Correct 33 ms 58456 KB Output is correct
7 Correct 35 ms 58712 KB Output is correct
8 Correct 44 ms 58620 KB Output is correct
9 Correct 52 ms 58876 KB Output is correct
10 Correct 33 ms 58456 KB Output is correct
11 Correct 51 ms 58884 KB Output is correct
12 Correct 56 ms 58968 KB Output is correct
13 Correct 44 ms 59044 KB Output is correct
14 Correct 50 ms 58864 KB Output is correct
15 Incorrect 88 ms 59840 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58456 KB Output is correct
2 Correct 30 ms 58456 KB Output is correct
3 Correct 30 ms 58456 KB Output is correct
4 Correct 31 ms 58508 KB Output is correct
5 Correct 31 ms 58448 KB Output is correct
6 Correct 33 ms 58456 KB Output is correct
7 Correct 35 ms 58712 KB Output is correct
8 Correct 44 ms 58620 KB Output is correct
9 Correct 52 ms 58876 KB Output is correct
10 Correct 33 ms 58456 KB Output is correct
11 Correct 51 ms 58884 KB Output is correct
12 Correct 56 ms 58968 KB Output is correct
13 Correct 44 ms 59044 KB Output is correct
14 Correct 50 ms 58864 KB Output is correct
15 Incorrect 88 ms 59840 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58456 KB Output is correct
2 Correct 30 ms 58456 KB Output is correct
3 Correct 30 ms 58456 KB Output is correct
4 Correct 31 ms 58508 KB Output is correct
5 Correct 31 ms 58448 KB Output is correct
6 Correct 33 ms 58456 KB Output is correct
7 Correct 35 ms 58712 KB Output is correct
8 Correct 44 ms 58620 KB Output is correct
9 Correct 52 ms 58876 KB Output is correct
10 Correct 33 ms 58456 KB Output is correct
11 Correct 51 ms 58884 KB Output is correct
12 Correct 56 ms 58968 KB Output is correct
13 Correct 44 ms 59044 KB Output is correct
14 Correct 50 ms 58864 KB Output is correct
15 Incorrect 88 ms 59840 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 58456 KB Output is correct
2 Correct 30 ms 58456 KB Output is correct
3 Correct 30 ms 58456 KB Output is correct
4 Correct 31 ms 58508 KB Output is correct
5 Correct 31 ms 58448 KB Output is correct
6 Correct 33 ms 58456 KB Output is correct
7 Correct 35 ms 58712 KB Output is correct
8 Correct 44 ms 58620 KB Output is correct
9 Correct 52 ms 58876 KB Output is correct
10 Correct 33 ms 58456 KB Output is correct
11 Correct 51 ms 58884 KB Output is correct
12 Correct 56 ms 58968 KB Output is correct
13 Correct 44 ms 59044 KB Output is correct
14 Correct 50 ms 58864 KB Output is correct
15 Incorrect 88 ms 59840 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -