Submission #492637

#	Time	Username	Problem	Language	Result	Execution time	Memory
492637		Jarif_Rahman	Monster Game (JOI21_monster)	C++17	10 / 100	114 ms	8172 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

#ifdef LOCAL
#define debug(v) for(auto x: v) cerr << x << " "; cerr << #v << "\n";
#endif

int do_cnt = 0;
int cnt = 0;

vector<vector<int>> QQ;
vector<vector<int>> extra;
bool query(int a, int b){
    if(a > b){
        extra[b][a] = 0;
        if(QQ[b][a] == -1) QQ[b][a] = Query(b, a), cnt+=do_cnt;
        return !QQ[b][a];
    }
    else{
        extra[a][b] = 0;
        if(QQ[a][b] == -1) QQ[a][b] = Query(a, b), cnt+=do_cnt;
        return QQ[a][b];
    }
}
bool query0(int a, int b){
    if(a > b){
        if(extra[b][a] == -1) extra[b][a] = 1; 
        if(QQ[b][a] == -1) QQ[b][a] = Query(b, a), cnt+=do_cnt;
        return !QQ[b][a];
    }
    else{
        if(extra[a][b] == -1) extra[a][b] = 1;
        if(QQ[a][b] == -1) QQ[a][b] = Query(a, b), cnt+=do_cnt;
        return QQ[a][b];
    }
}

template<typename it>
void merge_sort(it a, it b){
    int n = b-a;
    if(n == 1) return;
    merge_sort(a, a+n/2);
    merge_sort(a+n/2, b);
    int* ab = new int[n];
    merge(a, a+n/2, a+n/2, b, ab, [](int x, int y){
        return query(y, x);
    });
    for(int i = 0; i < n; i++) *(a+i) = *(ab+i);
}

vector<int> Solve(int n){
    QQ = vector<vector<int>>(n, vector<int>(n, -1));
    extra = QQ;

    vector<int> sth(n);
    for(int i = 0; i < n; i++) sth[i] = i;
    do_cnt = 1;
    merge_sort(sth.begin(), sth.end());

    int cnt2 = 0;

    auto win = [&](int x){
        vector<int> rt;
        for(int i = 0; i < n; i++) if(i != x && query0(x, i)) rt.pb(i);
        return rt;
    };

    int n0 = n;
    
    for(int i = 0; i < n0-1; i++){
        if(i == 0){
            auto s0 = win(sth[0]);
            if(s0.size() == 1){
                auto s1 = win(s0[0]);
                if(s1.size() == 1){
                    continue;
                }
            }
        }
        if(i != 0 && query(sth[i-1], sth[i])) continue;
        bool bl = 0;
        for(int j = i+2; j < n0; j++){
            if(query(sth[j], sth[j-2])){
                if((i == 0 && win(sth[j-1]).size() != 1) ||
                    (i != 0 && !query(sth[i-1], sth[j-1]))) 
                    reverse(sth.begin()+i, sth.begin()+j-1);
                else reverse(sth.begin()+i, sth.begin()+j);
                i = j-1;
                bl = 1;
                break;
            }
        }
        if(!bl){
            if((i == 0 && win(sth[n0-1]).size() != 1) ||
                (i != 0 && !query(sth[i-1], sth[n0-1])))
                reverse(sth.begin()+i, sth.begin()+n0-1);
            else reverse(sth.begin()+i, sth.begin()+n0);
            i = n0;
        }
    }

    if(cnt > 10000) exit(-1);

    vector<int> ans(n);
    for(int i = 0; i < n; i++) ans[sth[i]] = i;
    return ans;

}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:66:9: warning: unused variable 'cnt2' [-Wunused-variable]
   66 |     int cnt2 = 0;
      |         ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75