oj.uz

답안 #922849

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
922849 2024-02-06T08:07:35 Z boris_mihov Minerals (JOI19_minerals) C++17
70 / 100
 64 ms 59988 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)
    {
        for (int i = 0 ; i < n ; ++i)
        {
            if (((i & (1 << bit)) > 0) != isIn[unique[i]])
            {
                query(unique[i]);
            }
        }

        for (int i = 0 ; i < n ; ++i)
        {
            int curr = countDiff;
            int next = query(second[i]);
            if (curr == next)
            {
                with[second[i]] |= (1 << bit);
            }
        }
    }

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 58448 KB Output is correct
2 Correct 31 ms 58456 KB Output is correct
3 Correct 39 ms 58448 KB Output is correct
4 Correct 31 ms 58456 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 58456 KB Output is correct
2 Correct 37 ms 58448 KB Output is correct
3 Correct 37 ms 58520 KB Output is correct
4 Correct 39 ms 58700 KB Output is correct
5 Correct 44 ms 58988 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 58448 KB Output is correct
2 Correct 31 ms 58456 KB Output is correct
3 Correct 39 ms 58448 KB Output is correct
4 Correct 31 ms 58456 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 37 ms 58448 KB Output is correct
7 Correct 37 ms 58520 KB Output is correct
8 Correct 39 ms 58700 KB Output is correct
9 Correct 44 ms 58988 KB Output is correct
10 Correct 39 ms 58480 KB Output is correct
11 Correct 44 ms 58708 KB Output is correct
12 Correct 49 ms 59064 KB Output is correct
13 Correct 55 ms 59272 KB Output is correct
14 Correct 42 ms 58984 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 58448 KB Output is correct
2 Correct 31 ms 58456 KB Output is correct
3 Correct 39 ms 58448 KB Output is correct
4 Correct 31 ms 58456 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 37 ms 58448 KB Output is correct
7 Correct 37 ms 58520 KB Output is correct
8 Correct 39 ms 58700 KB Output is correct
9 Correct 44 ms 58988 KB Output is correct
10 Correct 39 ms 58480 KB Output is correct
11 Correct 44 ms 58708 KB Output is correct
12 Correct 49 ms 59064 KB Output is correct
13 Correct 55 ms 59272 KB Output is correct
14 Correct 42 ms 58984 KB Output is correct
15 Correct 57 ms 59800 KB Output is correct
16 Correct 64 ms 59988 KB Output is correct
17 Correct 60 ms 59944 KB Output is correct
18 Correct 57 ms 59760 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 58448 KB Output is correct
2 Correct 31 ms 58456 KB Output is correct
3 Correct 39 ms 58448 KB Output is correct
4 Correct 31 ms 58456 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 37 ms 58448 KB Output is correct
7 Correct 37 ms 58520 KB Output is correct
8 Correct 39 ms 58700 KB Output is correct
9 Correct 44 ms 58988 KB Output is correct
10 Correct 39 ms 58480 KB Output is correct
11 Correct 44 ms 58708 KB Output is correct
12 Correct 49 ms 59064 KB Output is correct
13 Correct 55 ms 59272 KB Output is correct
14 Correct 42 ms 58984 KB Output is correct
15 Correct 57 ms 59800 KB Output is correct
16 Correct 64 ms 59988 KB Output is correct
17 Correct 60 ms 59944 KB Output is correct
18 Correct 57 ms 59760 KB Output is correct
19 Incorrect 59 ms 59840 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 58448 KB Output is correct
2 Correct 31 ms 58456 KB Output is correct
3 Correct 39 ms 58448 KB Output is correct
4 Correct 31 ms 58456 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 37 ms 58448 KB Output is correct
7 Correct 37 ms 58520 KB Output is correct
8 Correct 39 ms 58700 KB Output is correct
9 Correct 44 ms 58988 KB Output is correct
10 Correct 39 ms 58480 KB Output is correct
11 Correct 44 ms 58708 KB Output is correct
12 Correct 49 ms 59064 KB Output is correct
13 Correct 55 ms 59272 KB Output is correct
14 Correct 42 ms 58984 KB Output is correct
15 Correct 57 ms 59800 KB Output is correct
16 Correct 64 ms 59988 KB Output is correct
17 Correct 60 ms 59944 KB Output is correct
18 Correct 57 ms 59760 KB Output is correct
19 Incorrect 59 ms 59840 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 58448 KB Output is correct
2 Correct 31 ms 58456 KB Output is correct
3 Correct 39 ms 58448 KB Output is correct
4 Correct 31 ms 58456 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 37 ms 58448 KB Output is correct
7 Correct 37 ms 58520 KB Output is correct
8 Correct 39 ms 58700 KB Output is correct
9 Correct 44 ms 58988 KB Output is correct
10 Correct 39 ms 58480 KB Output is correct
11 Correct 44 ms 58708 KB Output is correct
12 Correct 49 ms 59064 KB Output is correct
13 Correct 55 ms 59272 KB Output is correct
14 Correct 42 ms 58984 KB Output is correct
15 Correct 57 ms 59800 KB Output is correct
16 Correct 64 ms 59988 KB Output is correct
17 Correct 60 ms 59944 KB Output is correct
18 Correct 57 ms 59760 KB Output is correct
19 Incorrect 59 ms 59840 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 58448 KB Output is correct
2 Correct 31 ms 58456 KB Output is correct
3 Correct 39 ms 58448 KB Output is correct
4 Correct 31 ms 58456 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 37 ms 58448 KB Output is correct
7 Correct 37 ms 58520 KB Output is correct
8 Correct 39 ms 58700 KB Output is correct
9 Correct 44 ms 58988 KB Output is correct
10 Correct 39 ms 58480 KB Output is correct
11 Correct 44 ms 58708 KB Output is correct
12 Correct 49 ms 59064 KB Output is correct
13 Correct 55 ms 59272 KB Output is correct
14 Correct 42 ms 58984 KB Output is correct
15 Correct 57 ms 59800 KB Output is correct
16 Correct 64 ms 59988 KB Output is correct
17 Correct 60 ms 59944 KB Output is correct
18 Correct 57 ms 59760 KB Output is correct
19 Incorrect 59 ms 59840 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 58448 KB Output is correct
2 Correct 31 ms 58456 KB Output is correct
3 Correct 39 ms 58448 KB Output is correct
4 Correct 31 ms 58456 KB Output is correct
5 Correct 32 ms 58456 KB Output is correct
6 Correct 37 ms 58448 KB Output is correct
7 Correct 37 ms 58520 KB Output is correct
8 Correct 39 ms 58700 KB Output is correct
9 Correct 44 ms 58988 KB Output is correct
10 Correct 39 ms 58480 KB Output is correct
11 Correct 44 ms 58708 KB Output is correct
12 Correct 49 ms 59064 KB Output is correct
13 Correct 55 ms 59272 KB Output is correct
14 Correct 42 ms 58984 KB Output is correct
15 Correct 57 ms 59800 KB Output is correct
16 Correct 64 ms 59988 KB Output is correct
17 Correct 60 ms 59944 KB Output is correct
18 Correct 57 ms 59760 KB Output is correct
19 Incorrect 59 ms 59840 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -