Submission #804145

#	Time	Username	Problem	Language	Result	Execution time	Memory
804145		fatemetmhr	Monster Game (JOI21_monster)	C++17	0 / 100	91 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);

    a[0] = 0;
    a[1] = 1;
    a[2] = 2;
    a[3] = 3;
    for(int i = 0; i < 4; i++)
        for(int j = 0; j < 4; j++) if(i != j)
            cnt[i] += assk(i, j);
    sort(a, a + 4, cmp);
    for(int i = 4; 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]]++;
        bool ok = false;
        if(lo >= 1 && !assk(i, a[lo - 1])){
            cnt[i]--;
            cnt[a[lo - 1]]++;
            ok = true;
        }
        if(!ok && hi + 1 < i && assk(i, a[hi + 1])){
            cnt[i]++;
            cnt[a[hi + 1]]--;
        }
        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: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75