oj.uz

Submission #836204

# Submission time Handle Problem Language Result Execution time Memory
836204 2023-08-24T08:42:28 Z _martynas Minerals (JOI19_minerals) C++14
80 / 100
 477 ms 28108 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], calls[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, all B are in
    // 2. all A are in, no 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;
    calls[scenario]++;
    cnt[scenario] += A.size();
    if(A.size() == 2) {
        if(scenario == 0 || scenario == 1) {
            resp = Query(*A.begin()); int nresp = Query(*B.begin());
            ops[scenario] += 2;
            if(resp != nresp) {
                // first of A and B are equal
                solve(set<int>{*A.begin()}, set<int>{*B.begin()});
                solve(set<int>{*A.rbegin()}, set<int>{*B.rbegin()});
            }
            else {
                solve(set<int>{*A.begin()}, set<int>{*B.rbegin()});
                solve(set<int>{*A.rbegin()}, set<int>{*B.begin()});
            }
            resp = nresp;
            return;
        }
        else if(scenario == 2) {
            resp = Query(*A.begin()); int nresp = Query(*B.begin());
            ops[scenario] += 2;
            if(resp == nresp) {
                // first of A and B are equal
                solve(set<int>{*A.begin()}, set<int>{*B.begin()});
                solve(set<int>{*A.rbegin()}, set<int>{*B.rbegin()});
            }
            else {
                solve(set<int>{*A.begin()}, set<int>{*B.rbegin()});
                solve(set<int>{*A.rbegin()}, set<int>{*B.begin()});
            }
            resp = nresp;
            return;
        }
    }
    // 
    set<int> C, D, E, F;
    // split A into C and D
    int split = ina == 0 ? A.size()/2 : (A.size()+1)/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 << calls[0] << " " << calls[1] << " " << calls[2] << "\n";
    cerr << cnt[0] << " " << cnt[1] << " " << cnt[2] << "\n"; 
    cerr << 1.0*ops[0]/calls[0] << " " << 1.0*ops[1]/calls[1] << " " << 1.0*ops[2]/calls[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 27 ms 3016 KB Output is correct
4 Correct 63 ms 5744 KB Output is correct
5 Correct 133 ms 10668 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 27 ms 3016 KB Output is correct
8 Correct 63 ms 5744 KB Output is correct
9 Correct 133 ms 10668 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 85 ms 7160 KB Output is correct
12 Correct 133 ms 10748 KB Output is correct
13 Correct 106 ms 10640 KB Output is correct
14 Correct 103 ms 10576 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 27 ms 3016 KB Output is correct
8 Correct 63 ms 5744 KB Output is correct
9 Correct 133 ms 10668 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 85 ms 7160 KB Output is correct
12 Correct 133 ms 10748 KB Output is correct
13 Correct 106 ms 10640 KB Output is correct
14 Correct 103 ms 10576 KB Output is correct
15 Correct 451 ms 26560 KB Output is correct
16 Correct 425 ms 26548 KB Output is correct
17 Correct 321 ms 26604 KB Output is correct
18 Correct 325 ms 26396 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 27 ms 3016 KB Output is correct
8 Correct 63 ms 5744 KB Output is correct
9 Correct 133 ms 10668 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 85 ms 7160 KB Output is correct
12 Correct 133 ms 10748 KB Output is correct
13 Correct 106 ms 10640 KB Output is correct
14 Correct 103 ms 10576 KB Output is correct
15 Correct 451 ms 26560 KB Output is correct
16 Correct 425 ms 26548 KB Output is correct
17 Correct 321 ms 26604 KB Output is correct
18 Correct 325 ms 26396 KB Output is correct
19 Correct 446 ms 27152 KB Output is correct
20 Correct 445 ms 27224 KB Output is correct
21 Correct 331 ms 27272 KB Output is correct
22 Correct 327 ms 27060 KB Output is correct

Subtask #6
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 27 ms 3016 KB Output is correct
8 Correct 63 ms 5744 KB Output is correct
9 Correct 133 ms 10668 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 85 ms 7160 KB Output is correct
12 Correct 133 ms 10748 KB Output is correct
13 Correct 106 ms 10640 KB Output is correct
14 Correct 103 ms 10576 KB Output is correct
15 Correct 451 ms 26560 KB Output is correct
16 Correct 425 ms 26548 KB Output is correct
17 Correct 321 ms 26604 KB Output is correct
18 Correct 325 ms 26396 KB Output is correct
19 Correct 446 ms 27152 KB Output is correct
20 Correct 445 ms 27224 KB Output is correct
21 Correct 331 ms 27272 KB Output is correct
22 Correct 327 ms 27060 KB Output is correct
23 Correct 451 ms 27912 KB Output is correct
24 Correct 477 ms 27936 KB Output is correct
25 Correct 360 ms 28032 KB Output is correct
26 Correct 333 ms 27768 KB Output is correct

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 27 ms 3016 KB Output is correct
8 Correct 63 ms 5744 KB Output is correct
9 Correct 133 ms 10668 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 85 ms 7160 KB Output is correct
12 Correct 133 ms 10748 KB Output is correct
13 Correct 106 ms 10640 KB Output is correct
14 Correct 103 ms 10576 KB Output is correct
15 Correct 451 ms 26560 KB Output is correct
16 Correct 425 ms 26548 KB Output is correct
17 Correct 321 ms 26604 KB Output is correct
18 Correct 325 ms 26396 KB Output is correct
19 Correct 446 ms 27152 KB Output is correct
20 Correct 445 ms 27224 KB Output is correct
21 Correct 331 ms 27272 KB Output is correct
22 Correct 327 ms 27060 KB Output is correct
23 Correct 451 ms 27912 KB Output is correct
24 Correct 477 ms 27936 KB Output is correct
25 Correct 360 ms 28032 KB Output is correct
26 Correct 333 ms 27768 KB Output is correct
27 Incorrect 429 ms 28108 KB Wrong Answer [2]
28 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 27 ms 3016 KB Output is correct
8 Correct 63 ms 5744 KB Output is correct
9 Correct 133 ms 10668 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 85 ms 7160 KB Output is correct
12 Correct 133 ms 10748 KB Output is correct
13 Correct 106 ms 10640 KB Output is correct
14 Correct 103 ms 10576 KB Output is correct
15 Correct 451 ms 26560 KB Output is correct
16 Correct 425 ms 26548 KB Output is correct
17 Correct 321 ms 26604 KB Output is correct
18 Correct 325 ms 26396 KB Output is correct
19 Correct 446 ms 27152 KB Output is correct
20 Correct 445 ms 27224 KB Output is correct
21 Correct 331 ms 27272 KB Output is correct
22 Correct 327 ms 27060 KB Output is correct
23 Correct 451 ms 27912 KB Output is correct
24 Correct 477 ms 27936 KB Output is correct
25 Correct 360 ms 28032 KB Output is correct
26 Correct 333 ms 27768 KB Output is correct
27 Incorrect 429 ms 28108 KB Wrong Answer [2]
28 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 27 ms 3016 KB Output is correct
8 Correct 63 ms 5744 KB Output is correct
9 Correct 133 ms 10668 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 85 ms 7160 KB Output is correct
12 Correct 133 ms 10748 KB Output is correct
13 Correct 106 ms 10640 KB Output is correct
14 Correct 103 ms 10576 KB Output is correct
15 Correct 451 ms 26560 KB Output is correct
16 Correct 425 ms 26548 KB Output is correct
17 Correct 321 ms 26604 KB Output is correct
18 Correct 325 ms 26396 KB Output is correct
19 Correct 446 ms 27152 KB Output is correct
20 Correct 445 ms 27224 KB Output is correct
21 Correct 331 ms 27272 KB Output is correct
22 Correct 327 ms 27060 KB Output is correct
23 Correct 451 ms 27912 KB Output is correct
24 Correct 477 ms 27936 KB Output is correct
25 Correct 360 ms 28032 KB Output is correct
26 Correct 333 ms 27768 KB Output is correct
27 Incorrect 429 ms 28108 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -