oj.uz

Submission #836165

# Submission time Handle Problem Language Result Execution time Memory
836165 2023-08-24T08:14:27 Z _martynas Minerals (JOI19_minerals) C++14
75 / 100
 468 ms 28016 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)
*/
int resp;
int ops[3], cnt[3];
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 scenario;
    if(ina == A.size() && inb == B.size()) scenario = 0;
    if(ina == A.size() && inb == 0) scenario = 1;
    if(ina == 0 && inb == 0) scenario = 2;
    cnt[scenario]++;
    // 
    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)) {
            resp = Query(*ita); in.insert(*ita);
            ops[scenario]++;
        }
        ita = next(ita);
    }
    while(ita != A.end()) {
        D.insert(*ita);
        // ensure no D are in
        if(in.count(*ita)) {
            resp = Query(*ita); in.erase(*ita);
            ops[scenario]++;
        }
        ita = next(ita);
    }
    // ------------------
    if(inb == 0) {
        // none of B are in
        for(int b : B) {
            int nresp = Query(b); in.insert(b);
            ops[scenario]++;
            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[scenario]++;
            if(nresp != resp) {
                F.insert(b);
                resp = nresp;
            }
            else {
                E.insert(b);
            }
        }
        solve(C, E), solve(F, D);
    }
    // cout << A.size() << " " << B.size() << " " << ops[scenario] << "\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);
    cerr << ops[0] << " " << ops[1] << " " << ops[2] << "\n"; 
    cerr << cnt[0] << " " << cnt[1] << " " << cnt[2] << "\n"; 
    cerr << 1.0*ops[0]/cnt[0] << " " << 1.0*ops[1]/cnt[1] << " " << 1.0*ops[2]/cnt[2] << "\n"; 
    // 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:33:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     assert(ina == A.size() || ina == 0);
      |            ~~~~^~~~~~~~~~~
minerals.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     assert(inb == B.size() || inb == 0);
      |            ~~~~^~~~~~~~~~~
minerals.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(ina == A.size() && inb == B.size()) scenario = 0;
      |        ~~~~^~~~~~~~~~~
minerals.cpp:40:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     if(ina == A.size() && inb == B.size()) scenario = 0;
      |                           ~~~~^~~~~~~~~~~
minerals.cpp:41:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     if(ina == A.size() && inb == 0) scenario = 1;
      |        ~~~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 28 ms 3024 KB Output is correct
4 Correct 63 ms 5772 KB Output is correct
5 Correct 136 ms 10652 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 28 ms 3024 KB Output is correct
8 Correct 63 ms 5772 KB Output is correct
9 Correct 136 ms 10652 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7248 KB Output is correct
12 Correct 142 ms 10712 KB Output is correct
13 Correct 114 ms 10768 KB Output is correct
14 Correct 114 ms 10672 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 28 ms 3024 KB Output is correct
8 Correct 63 ms 5772 KB Output is correct
9 Correct 136 ms 10652 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7248 KB Output is correct
12 Correct 142 ms 10712 KB Output is correct
13 Correct 114 ms 10768 KB Output is correct
14 Correct 114 ms 10672 KB Output is correct
15 Correct 455 ms 26888 KB Output is correct
16 Correct 455 ms 26932 KB Output is correct
17 Correct 388 ms 26972 KB Output is correct
18 Correct 344 ms 26732 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 28 ms 3024 KB Output is correct
8 Correct 63 ms 5772 KB Output is correct
9 Correct 136 ms 10652 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7248 KB Output is correct
12 Correct 142 ms 10712 KB Output is correct
13 Correct 114 ms 10768 KB Output is correct
14 Correct 114 ms 10672 KB Output is correct
15 Correct 455 ms 26888 KB Output is correct
16 Correct 455 ms 26932 KB Output is correct
17 Correct 388 ms 26972 KB Output is correct
18 Correct 344 ms 26732 KB Output is correct
19 Correct 455 ms 27592 KB Output is correct
20 Correct 468 ms 27716 KB Output is correct
21 Correct 353 ms 27684 KB Output is correct
22 Correct 368 ms 27464 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 28 ms 3024 KB Output is correct
8 Correct 63 ms 5772 KB Output is correct
9 Correct 136 ms 10652 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7248 KB Output is correct
12 Correct 142 ms 10712 KB Output is correct
13 Correct 114 ms 10768 KB Output is correct
14 Correct 114 ms 10672 KB Output is correct
15 Correct 455 ms 26888 KB Output is correct
16 Correct 455 ms 26932 KB Output is correct
17 Correct 388 ms 26972 KB Output is correct
18 Correct 344 ms 26732 KB Output is correct
19 Correct 455 ms 27592 KB Output is correct
20 Correct 468 ms 27716 KB Output is correct
21 Correct 353 ms 27684 KB Output is correct
22 Correct 368 ms 27464 KB Output is correct
23 Incorrect 457 ms 28016 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 28 ms 3024 KB Output is correct
8 Correct 63 ms 5772 KB Output is correct
9 Correct 136 ms 10652 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7248 KB Output is correct
12 Correct 142 ms 10712 KB Output is correct
13 Correct 114 ms 10768 KB Output is correct
14 Correct 114 ms 10672 KB Output is correct
15 Correct 455 ms 26888 KB Output is correct
16 Correct 455 ms 26932 KB Output is correct
17 Correct 388 ms 26972 KB Output is correct
18 Correct 344 ms 26732 KB Output is correct
19 Correct 455 ms 27592 KB Output is correct
20 Correct 468 ms 27716 KB Output is correct
21 Correct 353 ms 27684 KB Output is correct
22 Correct 368 ms 27464 KB Output is correct
23 Incorrect 457 ms 28016 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 28 ms 3024 KB Output is correct
8 Correct 63 ms 5772 KB Output is correct
9 Correct 136 ms 10652 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7248 KB Output is correct
12 Correct 142 ms 10712 KB Output is correct
13 Correct 114 ms 10768 KB Output is correct
14 Correct 114 ms 10672 KB Output is correct
15 Correct 455 ms 26888 KB Output is correct
16 Correct 455 ms 26932 KB Output is correct
17 Correct 388 ms 26972 KB Output is correct
18 Correct 344 ms 26732 KB Output is correct
19 Correct 455 ms 27592 KB Output is correct
20 Correct 468 ms 27716 KB Output is correct
21 Correct 353 ms 27684 KB Output is correct
22 Correct 368 ms 27464 KB Output is correct
23 Incorrect 457 ms 28016 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 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 28 ms 3024 KB Output is correct
8 Correct 63 ms 5772 KB Output is correct
9 Correct 136 ms 10652 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 86 ms 7248 KB Output is correct
12 Correct 142 ms 10712 KB Output is correct
13 Correct 114 ms 10768 KB Output is correct
14 Correct 114 ms 10672 KB Output is correct
15 Correct 455 ms 26888 KB Output is correct
16 Correct 455 ms 26932 KB Output is correct
17 Correct 388 ms 26972 KB Output is correct
18 Correct 344 ms 26732 KB Output is correct
19 Correct 455 ms 27592 KB Output is correct
20 Correct 468 ms 27716 KB Output is correct
21 Correct 353 ms 27684 KB Output is correct
22 Correct 368 ms 27464 KB Output is correct
23 Incorrect 457 ms 28016 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -