oj.uz

Submission #552050

# Submission time Handle Problem Language Result Execution time Memory
552050 2022-04-22T10:08:16 Z RaresFelix Monster Game (JOI21_monster) C++17
88 / 100
 126 ms 1904 KB 
#include "monster.h"
#include <bits/stdc++.h>

using namespace std;
namespace da {
    int query_count = 0;
}
namespace {
    map<pair<int, int>, bool> R;
}  // namespace
bool cmp(int st, int dr) {
    if(R.count({st, dr})) return R[{st, dr}];
    else {
        ++da::query_count;
        R[{dr, st}] = !(R[{st, dr}] = Query(st, dr));
        return R[{st, dr}];
    }
}
bool is_cand(int p, int n) {
    int nr = 0;
    for(int i = 0; i < n; ++i)
        if(i != p) nr += cmp(p, i);
    return nr == 1;
}
using vi = vector<int>;
void mrg_srt(vi &O, vi &tmp, int st, int dr) {
    if(st == dr) return;
    int mij = (st + dr) >> 1;
    mrg_srt(O, tmp, st, mij);
    mrg_srt(O, tmp, mij + 1, dr);
    int p1 = st, p2 = mij + 1, pf = st;
    while(p1 <= mij && p2 <= dr) 
        tmp[pf++] = cmp(O[p1], O[p2]) ? O[p2++] : O[p1++];
    while(p1 <= mij) tmp[pf++] = O[p1++];
    while(p2 <= dr) tmp[pf++] = O[p2++];
    for(int i = st; i <= dr; ++i) O[i] = tmp[i];
}
vector<int> Solve(int n) {
    vector<int> O(n), Tmp(n);
    for(int i = 0; i < n; ++i) O[i] = i;
    mrg_srt(O, Tmp, 0, n - 1);
    //printf("Sort Init: %d\n", da::query_count);
    vector<int> OC;
    for(int i = 0; i < 3; ++i) if(is_cand(O[i], n)) OC.push_back(O[i]);
    int lgp = 2;
    for(int i = 0; i < n - 2; ++i) {
        if(cmp(O[i], O[i + 2]))
            lgp = i + 2;
        else break;
    }
    for(int i = lgp; i >= max(lgp-2, 3); --i) if(is_cand(O[i], n)) OC.push_back(O[i]);


    int zero;
    if(OC.size() == 2)
        zero = cmp(OC[0], OC[1]) ? OC[0] : OC[1];
    else zero = OC[0];
    //printf("Det0: %d\n", da::query_count);

    vector<int> NewO;
    NewO.push_back(zero);
    for(int i = 0; i < n; ++i)
        if(O[i] != zero) NewO.push_back(O[i]); 
    int start = 1;
    for(int i = 1; i < n; ++i) {
        if(cmp(NewO[start-1], NewO[i])) { // urmatorul
            reverse(NewO.data() + start, NewO.data() + i + 1);
            start = i + 1;
        }
    }
    vector<int> R(n);
    //printf("Fin: %d\n", da::query_count);
//    for(int i = 0; i < n; ++i) cerr << R[i] << " "; cerr << "\n";
    //for(int i = 0; i < n; ++i) cerr << NewO[i] << " "; cerr << "\n";
    for(int i = 0; i < n; ++i) R[NewO[i]] = i;
    return R;
}

Subtask #1
10.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 208 KB Output is correct
4 Correct 0 ms 220 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 3 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 18 ms 456 KB Output is correct
17 Correct 17 ms 520 KB Output is correct
18 Correct 20 ms 460 KB Output is correct
19 Correct 19 ms 492 KB Output is correct
20 Correct 18 ms 496 KB Output is correct
21 Correct 1 ms 208 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 1 ms 208 KB Output is correct
24 Correct 1 ms 208 KB Output is correct
25 Correct 1 ms 208 KB Output is correct
26 Correct 12 ms 504 KB Output is correct
27 Correct 1 ms 208 KB Output is correct
28 Correct 1 ms 208 KB Output is correct
29 Correct 1 ms 208 KB Output is correct
30 Correct 2 ms 208 KB Output is correct
31 Correct 0 ms 208 KB Output is correct
32 Correct 13 ms 424 KB Output is correct

Subtask #2
15.0 / 15.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 208 KB Output is correct
4 Correct 0 ms 220 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 0 ms 208 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 3 ms 208 KB Output is correct
13 Correct 1 ms 208 KB Output is correct
14 Correct 1 ms 208 KB Output is correct
15 Correct 1 ms 208 KB Output is correct
16 Correct 18 ms 456 KB Output is correct
17 Correct 17 ms 520 KB Output is correct
18 Correct 20 ms 460 KB Output is correct
19 Correct 19 ms 492 KB Output is correct
20 Correct 18 ms 496 KB Output is correct
21 Correct 1 ms 208 KB Output is correct
22 Correct 0 ms 208 KB Output is correct
23 Correct 1 ms 208 KB Output is correct
24 Correct 1 ms 208 KB Output is correct
25 Correct 1 ms 208 KB Output is correct
26 Correct 12 ms 504 KB Output is correct
27 Correct 1 ms 208 KB Output is correct
28 Correct 1 ms 208 KB Output is correct
29 Correct 1 ms 208 KB Output is correct
30 Correct 2 ms 208 KB Output is correct
31 Correct 0 ms 208 KB Output is correct
32 Correct 13 ms 424 KB Output is correct
33 Correct 108 ms 1720 KB Output is correct
34 Correct 91 ms 1772 KB Output is correct
35 Correct 101 ms 1792 KB Output is correct
36 Correct 112 ms 1732 KB Output is correct
37 Correct 113 ms 1760 KB Output is correct
38 Correct 98 ms 1836 KB Output is correct
39 Correct 106 ms 1732 KB Output is correct
40 Correct 105 ms 1752 KB Output is correct
41 Correct 126 ms 1724 KB Output is correct
42 Correct 103 ms 1812 KB Output is correct
43 Correct 75 ms 1340 KB Output is correct
44 Correct 64 ms 1304 KB Output is correct

Subtask #3
63.0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 113 ms 1736 KB Partially correct
2 Partially correct 109 ms 1732 KB Partially correct
3 Partially correct 107 ms 1716 KB Partially correct
4 Partially correct 62 ms 1728 KB Partially correct
5 Partially correct 106 ms 1824 KB Partially correct
6 Partially correct 93 ms 1540 KB Partially correct
7 Partially correct 91 ms 1624 KB Partially correct
8 Partially correct 121 ms 1716 KB Partially correct
9 Partially correct 117 ms 1756 KB Partially correct
10 Partially correct 85 ms 1904 KB Partially correct
11 Partially correct 63 ms 1764 KB Partially correct
12 Partially correct 65 ms 1712 KB Partially correct
13 Partially correct 88 ms 1592 KB Partially correct
14 Partially correct 84 ms 1532 KB Partially correct
15 Correct 72 ms 1404 KB Output is correct
16 Correct 70 ms 1288 KB Output is correct
17 Partially correct 68 ms 1712 KB Partially correct
18 Correct 74 ms 1224 KB Output is correct