Submission #423514

#	Time	Username	Problem	Language	Result	Execution time	Memory
423514		benedict0724	Monster Game (JOI21_monster)	C++17	0 / 100	102 ms	4192 KiB

monster

#include "monster.h"
using namespace std;
vector<int> now, tmp;

int w[1002][1002];

int fight(int i, int j)
{
    if(i == j) return 0;
    if(w[i][j] == -1)
    {
        w[i][j] = Query(i, j);
        w[j][i] = !w[i][j];
    }
    return w[i][j];
}

void dnc(int l, int r)
{
    if(l == r) return;
    int m = (l + r)/2;
    dnc(l, m);
    dnc(m+1, r);
    for(int i=l,j=m+1,k=l;k<=r;k++)
    {
        if(i == m+1) tmp[k] = now[j++];
        else if(j == r+1) tmp[k] = now[i++];
        else if(fight(now[i], now[j]) == 0)
            tmp[k] = now[i++];
        else
            tmp[k] = now[j++];
    }
    for(int i=l;i<=r;i++) now[i] = tmp[i];
}

vector<int> Solve(int N) {
    vector<int> T(N);
    now.resize(N);
    tmp.resize(N);

    for(int i=0;i<N;i++) now[i] = i;
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) w[i][j] = -1;
    dnc(0, N-1);
    for(int i=0;i<N;)
    {
        if(i == N-1) break;
        else if(i == N-2) { swap(now[i], now[i+1]); break; }
        else if(i == N-3)
        {
            if(fight(now[i-1], now[i])) swap(now[i+1], now[i+2]);
            else swap(now[i], now[i+1]);
            break;
        }
        else
        {
            int a = fight(now[i], now[i+2]);
            int b = fight(now[i+1], now[i+3]);
            if(a == 1 && b == 1)
            {
                swap(now[i+1], now[i+2]);
                i += 4;
                continue;
            }
            else if(a == 0 && b == 0)
            {
                swap(now[i], now[i+1]);
                swap(now[i+2], now[i+3]);
                i += 4;
                continue;
            }
            else
            {
                int c = fight(now[i+2], now[i+4]);
                if(c == 1)
                {
                    swap(now[i], now[i+1]);
                    swap(now[i+3], now[i+4]);
                    i += 5;
                    continue;
                }
                else
                {
                    swap(now[i+1], now[i+2]);
                    swap(now[i+3], now[i+4]);
                    i += 5;
                    continue;
                }
            }
        }
    }

    for(int i=0;i<N;i++) T[now[i]] = i;
    return T;
}

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