Submission #804271

#	Time	Username	Problem	Language	Result	Execution time	Memory
804271		fatemetmhr	Monster Game (JOI21_monster)	C++17	77 / 100	171 ms	4352 KiB

monster

//  ~ Be Name Khoda ~  //

#include "monster.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e3   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

namespace {

int a[maxn5], cnt[maxn5], done[maxn5][maxn5];

bool assk(int a, int b){
    if(done[a][b] == -1){
        done[a][b] = Query(a, b);
        done[b][a] = done[a][b] ^ 1;
    }
    return done[a][b];
}

bool cmp(int i, int j){return cnt[i] < cnt[j] || (cnt[i] == cnt[j] && assk(i, j));}


}  // namespace

std::vector<int> Solve(int n) {
    std::vector<int> ret(n);

    memset(done, -1, sizeof done);

    for(int i = 1; i < n; i++){
        int lo = -1, hi = i;
        while(hi - lo > 1){
            int mid = (lo + hi) >> 1;
            if(assk(a[mid], i))
                hi = mid;
            else
                lo = mid;
        }
        cnt[i] = lo + 1;
        for(int j = hi; j < i; j++)
            cnt[a[j]]++;
        for(int j = max(0, lo - 4); j < lo; j++) if(!assk(i, a[j])){
            cnt[a[j]]++;
            cnt[i]--;
            //cout << "ha? " << i << ' ' << j << ' ' << a[j] << endl;
        }
        for(int j = hi + 1; j < min(i, hi + 5); j++) if(assk(i, a[j])){
            cnt[a[j]]--;
            cnt[i]++;
        }
        //cout << "* " << i << ' ' << lo << ' ' << hi << ' ' << cnt[i] << ' ' << cnt[0] << endl;
        a[i] = i;
        sort(a, a + i + 1, cmp);
    }
    /*
    for(int i = 0; i < n; i++)
        cout << a[i] << ' ' << cnt[a[i]] << endl;
    cout << endl;
    //*/

    for (int i = 0; i < n; i++)
        ret[a[i]] = i;

    return ret;
}

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