Submission #1050823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050823		Andrey	Monster Game (JOI21_monster)	C++17	91 / 100	59 ms	596 KiB

monster

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

vector<int> haha(0);

void dude(int l, int r) {
    if(l == r) {
        return;
    }
    int mid = (l+r)/2;
    dude(l,mid);
    dude(mid+1,r);
    vector<int> wow(0);
    int x = l,y = mid+1;
    for(int i = 0; i < r-l+1; i++) {
        if(x != mid+1 && (y == r+1 || Query(haha[y],haha[x]))) {
            wow.push_back(haha[x]);
            x++;
        }
        else {
            wow.push_back(haha[y]);
            y++;
        }
    }
    for(int i = 0; i < wow.size(); i++) {
        haha[i+l] = wow[i];
    }
}

vector<int> Solve(int n) {
    for(int i = 0; i < n; i++) {
        haha.push_back(i);
    }
    dude(0,n-1);
    vector<bool> bruh(n);
    int big = 0;
    for(int i = 1; i < n; i++) {
        bruh[i] = Query(haha[0],haha[i]);
        if(bruh[i]) {
            big = i;
        }
    }
    int p = big-1;
    vector<int> ans(n);
    if(big == 2) {
        p = 1;
        for(int i = 3; i < n; i++) {
            if(Query(haha[1],haha[i])) {
                p = 0;
            }
        }
    }
    else {
        if(Query(haha[p],haha[0])) {
            p--;
            while(p > 0 && Query(haha[p],haha[big])) {
                p--;
            }
            if(p == 0 && Query(haha[0],haha[big-1])) {
                p--;
            }
        }
    }
    for(int i = p; i >= 0; i--) {
        ans[haha[i]] = p-i;
    }
    for(int i = p+1; i <= big; i++) {
        ans[haha[i]] = big-(i-p-1);
    }
    int y = p+1,x = big+1;
    for(int i = big+1; i < n; i++) {
        if(Query(haha[y],haha[i])) {
            for(int j = x; j <= i; j++) {
                ans[haha[j]] = i-(j-x);
            }
            y = x;
            x = i+1;
        }
    }
    return ans;
}

Compilation message (stderr)

monster.cpp: In function 'void dude(int, int)':
monster.cpp:26:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |     for(int i = 0; i < wow.size(); i++) {
      |                    ~~^~~~~~~~~~~~

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