Submission #1050938

#	Time	Username	Problem	Language	Result	Execution time	Memory
1050938		Andrey	Monster Game (JOI21_monster)	C++17	100 / 100	50 ms	592 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<int> ans(n);
    bool yeah = true;
    vector<bool> bruh(n);
    int big;
    for(int i = 2; i < n; i++) {
        if(Query(haha[0],haha[i])) {
            bruh[i] = true;
            if(!yeah) {
                big = i;
                break;
            }
        }
        else {
            if(yeah && ((i == 3) || (i >= 3 && Query(haha[i-1],haha[1])))) {
                big = i-1;
                yeah = false;
                break;
            }
            yeah = false;
        }
    }
    if(yeah) {
        if(Query(haha[n-1],haha[1])) {
            for(int i = 0; i < n-1; i++) {
                ans[haha[i]] = n-2-i;
            }
            ans[haha[n-1]] = n-1;
        }
        else {
            for(int i = 0; i < n; i++) {
                ans[haha[i]] = n-1-i;
            }
        }
        return ans;
    }
 /*   for(int i = 0; i < n; i++) {
        cout << haha[i] << " ";
    }
    cout << endl;*/
    int p = big-1;
    bool no = true;
    if(big == 2) {
        no = false;
        if(Query(haha[0],haha[3])) {
            ans[haha[0]] = 2;
            ans[haha[1]] = 1;
            ans[haha[2]] = 0;
            ans[haha[3]] = 3;
            p = 2;
            big = 3;
        }
        else if(Query(haha[1],haha[3])) {
            ans[haha[0]] = 0;
            ans[haha[1]] = 2;
            ans[haha[2]] = 1;
            ans[haha[3]] = 3;
            p = 2;
            big = 3;
        }
        else if(Query(haha[2],haha[3])) {
            ans[haha[0]] = 1;
            ans[haha[1]] = 0;
            ans[haha[2]] = 2;
            ans[haha[3]] = 3;
            p = 2;
            big = 3;
        }
        else {
            int q;
            for(int i = 5; i <= n; i++) {
                if(Query(haha[0],haha[i-1]) || Query(haha[1],haha[i-1]) || Query(haha[2],haha[i-1])) {
                    q = i-1;
                    break;
                }
                if(i == n || (!Query(haha[3],haha[i]))) {
                    if(Query(haha[0],haha[i-1]) || Query(haha[1],haha[i-1]) || Query(haha[2],haha[i-1])) {
                        q = i-1;
                    }
                    else {
                        q = i-2;
                    }
                }
            }
            if(Query(haha[0],haha[q])) {
                ans[haha[0]] = 2;
                ans[haha[1]] = 1;
                ans[haha[2]] = 0;
            }
            else if(Query(haha[1],haha[q])) {
                ans[haha[0]] = 0;
                ans[haha[1]] = 2;
                ans[haha[2]] = 1;
            }
            else if(Query(haha[2],haha[q])) {
                ans[haha[0]] = 1;
                ans[haha[1]] = 0;
                ans[haha[2]] = 2;
            }
            else {
                cout << 1/0 << endl;
            }
            for(int i = 3; i <= q; i++) {
                ans[haha[i]] = q-(i-3);
            }
            big = q;
            p = 2;
        }
    }
    else {
        while(p > 1 && !bruh[p]) {
            p--;
        }
        if(p == 1 && Query(haha[1],haha[big])) {
            p--;
        }
    }
   /* for(int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;*/
    if(no) {
        for(int i = 0; i <= p; 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++) {
      |                    ~~^~~~~~~~~~~~
monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:135:26: warning: division by zero [-Wdiv-by-zero]
  135 |                 cout << 1/0 << endl;
      |                         ~^~
monster.cpp:75:9: warning: 'big' may be used uninitialized in this function [-Wmaybe-uninitialized]
   75 |     int p = big-1;
      |         ^
monster.cpp:119:36: warning: 'q' may be used uninitialized in this function [-Wmaybe-uninitialized]
  119 |             if(Query(haha[0],haha[q])) {
      |                                    ^

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