Submission #891324

#	Time	Username	Problem	Language	Result	Execution time	Memory
891324		lolicon	Monster Game (JOI21_monster)	C++17	10 / 100	108 ms	4432 KiB

monster

#include <bits/stdc++.h>
#include "monster.h"
using namespace std;

static vector<vector<int>> table;
static int n;

bool query(int a, int b) {
    if(table[a][b] != -1) return table[a][b];
    bool res = Query(a, b);
    table[a][b] = res ? 1 : 0;
    table[b][a] = res ? 0 : 1;
    return res;
}

bool test(int a, int b) {
    bool res = query(a, b);    
    int cnta = 0, cntb = 0;
    for(int i = 0; i < n; ++i) {
        if(i != a && query(a, i)) cnta++;
        if(i != b && query(b, i)) cntb++;
    }
    if(cnta == cntb) 
        return !res;
    if(!res && cnta == cntb+1)
        return !res;
    if(res && cnta+1 == cntb)
        return !res;
    return res;
    // static int arr[] = {3, 1, 4, 2, 0};
    // return arr[a] > arr[b];
}

void merge_sort(int l, int r, vector<int> &arr, vector<int> &buf) {
    if(r - l <= 1) return;
    int mid = (l + r) >> 1;
    merge_sort(l, mid, arr, buf);
    merge_sort(mid, r, arr, buf);
    int i, j, idx = l;
    for(i = l, j = mid; i < mid; ++i) {
        while(j < r && test(arr[i], arr[j])) {
            buf[idx++] = arr[j++];
        }
        buf[idx++] = arr[i];
    }
    while(j < r) buf[idx++] = arr[j++];
    for(idx = l; idx < r; ++idx)
        arr[idx] = buf[idx];
}

vector<int> Solve(int N) {
    vector<int> arr(N), buf(N);
    table.resize(N); n = N;
    for(int i = 0; i < N; ++i) 
        table[i].assign(N, -1);
    for(int i = 0; i < N; ++i) 
        arr[i] = i;
    merge_sort(0, N, arr, buf);
    vector<int> ret(N);
    for(int i = 0; i < N; ++i)  
        ret[arr[i]] = i;
    return ret;
}


#ifdef local

int main() {
    auto ans = Solve(5);
    for(int i = 0; i < 5; ++i) {
        printf("%d%c", ans[i], " \n"[i == 4]);
    }
    return 0;
}

#endif

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