oj.uz

Submission #836157

# Submission time Handle Problem Language Result Execution time Memory
836157 2023-08-24T08:05:12 Z _martynas Minerals (JOI19_minerals) C++14
40 / 100
 400 ms 26312 KB 
#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;

set<int> in;
map<int, int> M;

/*
solve(A, B)
A -> C D
B -> E F
solve(C, E), solve(F, D)
*/
void solve(set<int> A, set<int> B) {
    assert(A.size() == B.size());
    if(A.empty()) return;
    // found a pair
    if(A.size() == 1) {
        M[*A.begin()] = *B.begin();
        return;
    }
    // check which scenario solve is in
    // 1. all A are in, no B are in
    // 2. all A are in, all B are in
    // 3. no A are in, no B are in
    int ina = 0;
    for(int a : A) {
        if(in.count(a)) ina++;
    }
    assert(ina == A.size() || ina == 0);
    int inb = 0;
    for(int b : B) {
        if(in.count(b)) inb++;
    }
    assert(inb == B.size() || inb == 0);
    // 
    int ops = 0;
    set<int> C, D, E, F;
    // split A into C and D
    int split = A.size()/2;
    auto ita = A.begin();
    for(int i = 0; i < split; i++) {
        C.insert(*ita);
        // ensure all C are in
        if(!in.count(*ita)) {
            Query(*ita); in.insert(*ita);
            ops++;
        }
        ita = next(ita);
    }
    while(ita != A.end()) {
        D.insert(*ita);
        // ensure no D are in
        if(in.count(*ita)) {
            Query(*ita); in.erase(*ita);
            ops++;
        }
        ita = next(ita);
    }
    // take and put back from C to get accurate resp value
    int resp; Query(*C.begin());
    ops++;
    resp = Query(*C.begin());
    ops++;
    // ------------------
    if(inb == 0) {
        // none of B are in
        for(int b : B) {
            int nresp = Query(b); in.insert(b);
            ops++;
            if(nresp != resp) {
                F.insert(b);
                resp = nresp;
            }
            else {
                E.insert(b);
            }
        }
        solve(C, E), solve(F, D);
    }
    else {
        // all from B are in
        for(int b : B) {
            int nresp = Query(b); in.erase(b);
            ops++;
            if(nresp != resp) {
                F.insert(b);
                resp = nresp;
            }
            else {
                E.insert(b);
            }
        }
        solve(C, E), solve(F, D);
    }
    // cout << A.size() << " " << B.size() << " " << ops << "\n";
}

void Solve(int N) {
    // sub2: all 1, 2, ..., N are in the first half and in the second half
    set<int> A, B;
    int resp = -1, nresp;
    for(int i = 1; i <= 2*N; i++) {
        nresp = Query(i);
        in.insert(i);
        if(resp != nresp) {
            A.insert(i);
            resp = nresp;
        }
        else {
            B.insert(i);
        }
    }
    solve(A, B);
    // for(auto p : M) {
    //     cout << p.first << " " << p.second << "\n";
    // }
    for(auto p : M) {
        Answer(p.first, p.second);
    }
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from minerals.cpp:2:
minerals.cpp: In function 'void solve(std::set<int>, std::set<int>)':
minerals.cpp:31:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     assert(ina == A.size() || ina == 0);
      |            ~~~~^~~~~~~~~~~
minerals.cpp:36:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     assert(inb == B.size() || inb == 0);
      |            ~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 976 KB Output is correct
2 Correct 12 ms 1616 KB Output is correct
3 Correct 32 ms 2984 KB Output is correct
4 Correct 64 ms 5832 KB Output is correct
5 Correct 134 ms 10780 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 976 KB Output is correct
6 Correct 12 ms 1616 KB Output is correct
7 Correct 32 ms 2984 KB Output is correct
8 Correct 64 ms 5832 KB Output is correct
9 Correct 134 ms 10780 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7244 KB Output is correct
12 Correct 143 ms 10676 KB Output is correct
13 Correct 116 ms 10708 KB Output is correct
14 Correct 112 ms 10652 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 976 KB Output is correct
6 Correct 12 ms 1616 KB Output is correct
7 Correct 32 ms 2984 KB Output is correct
8 Correct 64 ms 5832 KB Output is correct
9 Correct 134 ms 10780 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7244 KB Output is correct
12 Correct 143 ms 10676 KB Output is correct
13 Correct 116 ms 10708 KB Output is correct
14 Correct 112 ms 10652 KB Output is correct
15 Incorrect 400 ms 26312 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 976 KB Output is correct
6 Correct 12 ms 1616 KB Output is correct
7 Correct 32 ms 2984 KB Output is correct
8 Correct 64 ms 5832 KB Output is correct
9 Correct 134 ms 10780 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7244 KB Output is correct
12 Correct 143 ms 10676 KB Output is correct
13 Correct 116 ms 10708 KB Output is correct
14 Correct 112 ms 10652 KB Output is correct
15 Incorrect 400 ms 26312 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 976 KB Output is correct
6 Correct 12 ms 1616 KB Output is correct
7 Correct 32 ms 2984 KB Output is correct
8 Correct 64 ms 5832 KB Output is correct
9 Correct 134 ms 10780 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7244 KB Output is correct
12 Correct 143 ms 10676 KB Output is correct
13 Correct 116 ms 10708 KB Output is correct
14 Correct 112 ms 10652 KB Output is correct
15 Incorrect 400 ms 26312 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 976 KB Output is correct
6 Correct 12 ms 1616 KB Output is correct
7 Correct 32 ms 2984 KB Output is correct
8 Correct 64 ms 5832 KB Output is correct
9 Correct 134 ms 10780 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7244 KB Output is correct
12 Correct 143 ms 10676 KB Output is correct
13 Correct 116 ms 10708 KB Output is correct
14 Correct 112 ms 10652 KB Output is correct
15 Incorrect 400 ms 26312 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 976 KB Output is correct
6 Correct 12 ms 1616 KB Output is correct
7 Correct 32 ms 2984 KB Output is correct
8 Correct 64 ms 5832 KB Output is correct
9 Correct 134 ms 10780 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7244 KB Output is correct
12 Correct 143 ms 10676 KB Output is correct
13 Correct 116 ms 10708 KB Output is correct
14 Correct 112 ms 10652 KB Output is correct
15 Incorrect 400 ms 26312 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 6 ms 976 KB Output is correct
6 Correct 12 ms 1616 KB Output is correct
7 Correct 32 ms 2984 KB Output is correct
8 Correct 64 ms 5832 KB Output is correct
9 Correct 134 ms 10780 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7244 KB Output is correct
12 Correct 143 ms 10676 KB Output is correct
13 Correct 116 ms 10708 KB Output is correct
14 Correct 112 ms 10652 KB Output is correct
15 Incorrect 400 ms 26312 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -