Submission #1136727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136727		danglayloi1	Monster Game (JOI21_monster)	C++20	92 / 100	27 ms	428 KiB

monster

#include <bits/stdc++.h>
#include "monster.h"
#define ii pair<int, int>
#define fi first
#define se second
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
using ll = long long;
const ll mod=1e9+7;
const int nx=1e3+5;
// int a[10];
// bool Query(int x, int y)
// {
//     if(abs(a[x]-a[y])==1)
//         return a[x]<a[y];
//     return a[x]>a[y];
// }
vector<int> cur;
vector<int> Solve(int n)
{
    cur.clear();
    cur.emplace_back(0);
    for(int i = 1; i < n; i++)
    {
        int d=0, c=cur.size()-1, g, pos=cur.size();
        while(d<=c)
        {
            g=(d+c)>>1;
            if(Query(cur[g], i))
                pos=g, c=g-1;
            else d=g+1;
        }
        cur.insert(cur.begin()+pos, i);
    }
    int st;
    int win=0;
    for(int i = 0; i < n; i++)
        if(i!=cur[0])
            win+=Query(cur[0], i);
    if(win==1)
    {
        int wii=0;
        for(int i = 0; i < n; i++)
            if(i!=cur[1])
                wii+=Query(cur[1], i);
        if(wii==1)
            st=1;
        else st=0;
    }
    else if(win==n-2)
    {
        int wii=0;
        for(int i = 0; i < n; i++)
            if(i!=cur[1])
                wii+=Query(cur[1], i);
        if(wii==n-2)
            st=n-1;
        else st=n-2;
    }
    else st=win;
    vector<int> res;
    res.resize(n);
    for(int i = 0; i <= st; i++)
        res[i]=st-i;
    ii p={0, st};
    int base=st+1;
    for(int i = st+1; i < n; i++)
    {
        if(Query(cur[p.fi], cur[i]))
        {
            for(int j = i; j > p.se; j--)
                res[j]=base++;
            p={p.se+1, i};
        }
    }
    vector<int> ans;
    ans.resize(n);
    for(int i = 0; i < n; i++)
        ans[cur[i]]=res[i];
    return ans;
}
// int main()
// {
//     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//     a[0]=3, a[1]=1, a[2]=4, a[3]=2, a[4]=0;
//     vector<int> tmp=Solve(5);
//     for(int c:tmp)
//         cout<<c<<' ';
// }

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