oj.uz

Submission #922853

# Submission time Handle Problem Language Result Execution time Memory
922853 2024-02-06T08:09:42 Z boris_mihov Minerals (JOI19_minerals) C++17
70 / 100
 68 ms 60048 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 with[MAXN];
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(69420);

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 last = 0;

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

    assert(unique.size() == n);
    assert(second.size() == n);
    
    for (int bit = 0 ; (1 << bit) < n ; ++bit)
    {
        int cntIn = 0;
        int cntOut = 0;
        for (int i = 0 ; i < n ; ++i)
        {
            if (((i & (1 << bit)) > 0) != isIn[unique[i]])
            {
                query(unique[i]);
            }

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

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

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

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

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

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:52:27: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         if (unique.size() < n && (second.size() == n || query(i) > last))
      |             ~~~~~~~~~~~~~~^~~
minerals.cpp:52:49: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         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:63:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |     assert(unique.size() == n);
      |            ~~~~~~~~~~~~~~^~~~
minerals.cpp:64:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     assert(second.size() == n);
      |            ~~~~~~~~~~~~~~^~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 58456 KB Output is correct
2 Correct 35 ms 58708 KB Output is correct
3 Correct 40 ms 58712 KB Output is correct
4 Correct 43 ms 58868 KB Output is correct
5 Correct 50 ms 59128 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58456 KB Output is correct
2 Correct 34 ms 58444 KB Output is correct
3 Correct 35 ms 58456 KB Output is correct
4 Correct 30 ms 58644 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 35 ms 58708 KB Output is correct
7 Correct 40 ms 58712 KB Output is correct
8 Correct 43 ms 58868 KB Output is correct
9 Correct 50 ms 59128 KB Output is correct
10 Correct 34 ms 58456 KB Output is correct
11 Correct 42 ms 58920 KB Output is correct
12 Correct 45 ms 59224 KB Output is correct
13 Correct 45 ms 59064 KB Output is correct
14 Correct 48 ms 58972 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58456 KB Output is correct
2 Correct 34 ms 58444 KB Output is correct
3 Correct 35 ms 58456 KB Output is correct
4 Correct 30 ms 58644 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 35 ms 58708 KB Output is correct
7 Correct 40 ms 58712 KB Output is correct
8 Correct 43 ms 58868 KB Output is correct
9 Correct 50 ms 59128 KB Output is correct
10 Correct 34 ms 58456 KB Output is correct
11 Correct 42 ms 58920 KB Output is correct
12 Correct 45 ms 59224 KB Output is correct
13 Correct 45 ms 59064 KB Output is correct
14 Correct 48 ms 58972 KB Output is correct
15 Correct 62 ms 59684 KB Output is correct
16 Correct 61 ms 59776 KB Output is correct
17 Correct 66 ms 59932 KB Output is correct
18 Correct 61 ms 60048 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58456 KB Output is correct
2 Correct 34 ms 58444 KB Output is correct
3 Correct 35 ms 58456 KB Output is correct
4 Correct 30 ms 58644 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 35 ms 58708 KB Output is correct
7 Correct 40 ms 58712 KB Output is correct
8 Correct 43 ms 58868 KB Output is correct
9 Correct 50 ms 59128 KB Output is correct
10 Correct 34 ms 58456 KB Output is correct
11 Correct 42 ms 58920 KB Output is correct
12 Correct 45 ms 59224 KB Output is correct
13 Correct 45 ms 59064 KB Output is correct
14 Correct 48 ms 58972 KB Output is correct
15 Correct 62 ms 59684 KB Output is correct
16 Correct 61 ms 59776 KB Output is correct
17 Correct 66 ms 59932 KB Output is correct
18 Correct 61 ms 60048 KB Output is correct
19 Incorrect 68 ms 59824 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58456 KB Output is correct
2 Correct 34 ms 58444 KB Output is correct
3 Correct 35 ms 58456 KB Output is correct
4 Correct 30 ms 58644 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 35 ms 58708 KB Output is correct
7 Correct 40 ms 58712 KB Output is correct
8 Correct 43 ms 58868 KB Output is correct
9 Correct 50 ms 59128 KB Output is correct
10 Correct 34 ms 58456 KB Output is correct
11 Correct 42 ms 58920 KB Output is correct
12 Correct 45 ms 59224 KB Output is correct
13 Correct 45 ms 59064 KB Output is correct
14 Correct 48 ms 58972 KB Output is correct
15 Correct 62 ms 59684 KB Output is correct
16 Correct 61 ms 59776 KB Output is correct
17 Correct 66 ms 59932 KB Output is correct
18 Correct 61 ms 60048 KB Output is correct
19 Incorrect 68 ms 59824 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58456 KB Output is correct
2 Correct 34 ms 58444 KB Output is correct
3 Correct 35 ms 58456 KB Output is correct
4 Correct 30 ms 58644 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 35 ms 58708 KB Output is correct
7 Correct 40 ms 58712 KB Output is correct
8 Correct 43 ms 58868 KB Output is correct
9 Correct 50 ms 59128 KB Output is correct
10 Correct 34 ms 58456 KB Output is correct
11 Correct 42 ms 58920 KB Output is correct
12 Correct 45 ms 59224 KB Output is correct
13 Correct 45 ms 59064 KB Output is correct
14 Correct 48 ms 58972 KB Output is correct
15 Correct 62 ms 59684 KB Output is correct
16 Correct 61 ms 59776 KB Output is correct
17 Correct 66 ms 59932 KB Output is correct
18 Correct 61 ms 60048 KB Output is correct
19 Incorrect 68 ms 59824 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58456 KB Output is correct
2 Correct 34 ms 58444 KB Output is correct
3 Correct 35 ms 58456 KB Output is correct
4 Correct 30 ms 58644 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 35 ms 58708 KB Output is correct
7 Correct 40 ms 58712 KB Output is correct
8 Correct 43 ms 58868 KB Output is correct
9 Correct 50 ms 59128 KB Output is correct
10 Correct 34 ms 58456 KB Output is correct
11 Correct 42 ms 58920 KB Output is correct
12 Correct 45 ms 59224 KB Output is correct
13 Correct 45 ms 59064 KB Output is correct
14 Correct 48 ms 58972 KB Output is correct
15 Correct 62 ms 59684 KB Output is correct
16 Correct 61 ms 59776 KB Output is correct
17 Correct 66 ms 59932 KB Output is correct
18 Correct 61 ms 60048 KB Output is correct
19 Incorrect 68 ms 59824 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 58456 KB Output is correct
2 Correct 34 ms 58444 KB Output is correct
3 Correct 35 ms 58456 KB Output is correct
4 Correct 30 ms 58644 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 35 ms 58708 KB Output is correct
7 Correct 40 ms 58712 KB Output is correct
8 Correct 43 ms 58868 KB Output is correct
9 Correct 50 ms 59128 KB Output is correct
10 Correct 34 ms 58456 KB Output is correct
11 Correct 42 ms 58920 KB Output is correct
12 Correct 45 ms 59224 KB Output is correct
13 Correct 45 ms 59064 KB Output is correct
14 Correct 48 ms 58972 KB Output is correct
15 Correct 62 ms 59684 KB Output is correct
16 Correct 61 ms 59776 KB Output is correct
17 Correct 66 ms 59932 KB Output is correct
18 Correct 61 ms 60048 KB Output is correct
19 Incorrect 68 ms 59824 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -