oj.uz

Submission #1057008

# Submission time Handle Problem Language Result Execution time Memory
1057008 2024-08-13T13:11:51 Z GrindMachine Monster Game (JOI21_monster) C++17
88 / 100
 85 ms 2420 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);
    };

    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    shuffle(all(a),rng);
    stable_sort(all(a),cmp);

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

        return ans;
    };

    vector<pii> blocks;
    
    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 1 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 0 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 1 ms 344 KB Output is correct
13 Correct 1 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 7 ms 600 KB Output is correct
18 Correct 8 ms 600 KB Output is correct
19 Correct 7 ms 472 KB Output is correct
20 Correct 7 ms 600 KB Output is correct
21 Correct 1 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 7 ms 504 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 1 ms 344 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 8 ms 600 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 0 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 1 ms 344 KB Output is correct
13 Correct 1 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 7 ms 600 KB Output is correct
18 Correct 8 ms 600 KB Output is correct
19 Correct 7 ms 472 KB Output is correct
20 Correct 7 ms 600 KB Output is correct
21 Correct 1 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 7 ms 504 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 1 ms 344 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 8 ms 600 KB Output is correct
33 Correct 53 ms 1756 KB Output is correct
34 Correct 51 ms 1892 KB Output is correct
35 Correct 55 ms 1880 KB Output is correct
36 Correct 71 ms 1864 KB Output is correct
37 Correct 61 ms 1872 KB Output is correct
38 Correct 58 ms 2128 KB Output is correct
39 Correct 66 ms 1872 KB Output is correct
40 Correct 66 ms 2040 KB Output is correct
41 Correct 66 ms 2420 KB Output is correct
42 Correct 61 ms 1924 KB Output is correct
43 Correct 68 ms 1872 KB Output is correct
44 Correct 65 ms 1616 KB Output is correct

Subtask #3
63.0 / 75.0

# Verdict Execution time Memory Grader output
1 Partially correct 72 ms 2108 KB Partially correct
2 Partially correct 63 ms 1904 KB Partially correct
3 Partially correct 68 ms 1904 KB Partially correct
4 Partially correct 75 ms 1972 KB Partially correct
5 Partially correct 66 ms 2128 KB Partially correct
6 Correct 49 ms 1656 KB Output is correct
7 Correct 34 ms 1504 KB Output is correct
8 Partially correct 73 ms 1876 KB Partially correct
9 Partially correct 85 ms 2076 KB Partially correct
10 Partially correct 58 ms 1616 KB Partially correct
11 Partially correct 75 ms 1840 KB Partially correct
12 Partially correct 62 ms 2212 KB Partially correct
13 Partially correct 45 ms 1636 KB Partially correct
14 Correct 46 ms 1776 KB Output is correct
15 Correct 29 ms 1680 KB Output is correct
16 Correct 44 ms 1344 KB Output is correct
17 Partially correct 61 ms 1872 KB Partially correct
18 Correct 28 ms 1112 KB Output is correct