oj.uz

Submission #1057004

# Submission time Handle Problem Language Result Execution time Memory
1057004 2024-08-13T13:07:06 Z GrindMachine Monster Game (JOI21_monster) C++17
88 / 100
 73 ms 2532 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/91295?#comment-801014

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "monster.h"

namespace {

bool example_variable;

}  // namespace

std::vector<int> Solve(int n) {
  // std::vector<int> T(N);

  // example_variable = Query(0, 1);

  // for (int i = 0; i < N; i++) T[i] = (N - 1) - i;

  // return T;

    vector<int> a(n);
    iota(all(a),0);
    map<pii,bool> mp;

    auto f = [&](int i, int j){
        if(mp.count({i,j})) return mp[{i,j}];
        bool res = Query(i,j);
        mp[{i,j}] = res, mp[{j,i}] = res^1;
        return res;
    };

    auto cmp = [&](int i, int j){
        return !f(i,j);
    };

    stable_sort(all(a),cmp);
    vector<pii> blocks;

    auto win_count = [&](int i){
        int ans = 0;
        rep(j,n){
            if(j != i){
                ans += f(i,j);
            }
        }

        return ans;
    };

    int win1 = win_count(a[0]);
    if(win1 > 1){
        blocks.pb({0,2});
        for(int i = 3; i < n; ++i){
            if(f(a[1],a[i])){
                blocks.back().ss++;
            }
            else{
                break;
            }
        }
    }
    else{
        int win2 = win_count(a[1]);
        if(win2 > 1){
            blocks.pb({0,0});
        }
        else{
            if(f(a[0],a[1])){
                blocks.pb({0,0});
                blocks.pb({1,1});
            }
            else{
                blocks.pb({0,1});
            }
        }
    }

    int s  = blocks.back().ss+1;
    for(int i = s; i < n; ++i){
        if(f(a[blocks.back().ff],a[i])){
            blocks.pb({blocks.back().ss+1,i});
        }
    }

    vector<int> ans(n);
    int ptr = 0;
    for(auto [l,r] : blocks){
        rev(i,r,l){
            ans[a[i]] = ptr++;
        }
    }

    return ans;
}

Compilation message

monster.cpp:65:6: warning: '{anonymous}::example_variable' defined but not used [-Wunused-variable]
   65 | bool example_variable;
      |      ^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 8 ms 600 KB Output is correct
17 Correct 8 ms 528 KB Output is correct
18 Correct 8 ms 600 KB Output is correct
19 Correct 8 ms 556 KB Output is correct
20 Correct 8 ms 600 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 5 ms 344 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 5 ms 344 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 8 ms 600 KB Output is correct
17 Correct 8 ms 528 KB Output is correct
18 Correct 8 ms 600 KB Output is correct
19 Correct 8 ms 556 KB Output is correct
20 Correct 8 ms 600 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 0 ms 344 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 0 ms 344 KB Output is correct
26 Correct 5 ms 344 KB Output is correct
27 Correct 0 ms 344 KB Output is correct
28 Correct 0 ms 344 KB Output is correct
29 Correct 0 ms 344 KB Output is correct
30 Correct 0 ms 344 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 5 ms 344 KB Output is correct
33 Correct 55 ms 2172 KB Output is correct
34 Correct 71 ms 2152 KB Output is correct
35 Correct 57 ms 1868 KB Output is correct
36 Correct 66 ms 1872 KB Output is correct
37 Correct 65 ms 2532 KB Output is correct
38 Correct 45 ms 1992 KB Output is correct
39 Correct 71 ms 1872 KB Output is correct
40 Correct 59 ms 1612 KB Output is correct
41 Correct 58 ms 1984 KB Output is correct
42 Correct 57 ms 1872 KB Output is correct
43 Correct 27 ms 1492 KB Output is correct
44 Correct 28 ms 1264 KB Output is correct

Subtask #3
63.0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 56 ms 1836 KB Partially correct
2 Partially correct 62 ms 1904 KB Partially correct
3 Partially correct 64 ms 1940 KB Partially correct
4 Partially correct 64 ms 1804 KB Partially correct
5 Partially correct 68 ms 2212 KB Partially correct
6 Correct 40 ms 1360 KB Output is correct
7 Correct 43 ms 1580 KB Output is correct
8 Partially correct 56 ms 1788 KB Partially correct
9 Partially correct 73 ms 2020 KB Partially correct
10 Partially correct 62 ms 1968 KB Partially correct
11 Partially correct 68 ms 2020 KB Partially correct
12 Partially correct 69 ms 1872 KB Partially correct
13 Partially correct 53 ms 1872 KB Partially correct
14 Correct 59 ms 1780 KB Output is correct
15 Correct 32 ms 1252 KB Output is correct
16 Correct 31 ms 1360 KB Output is correct
17 Partially correct 71 ms 1872 KB Partially correct
18 Correct 34 ms 1252 KB Output is correct