Submission #421124

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
421124	2021-06-08 18:22:18	Berted	Monster Game (JOI21_monster)	C++17	100 / 100	115 ms	4168 KiB

monster

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "monster.h"
#include <random>
#include <iostream>
#include <algorithm>
#define vi vector<int>
#define uid uniform_int_distribution<int>
using namespace std;
/*
    Observations:
    - P_i will win against min(1, max(P_i, N - 2)) opponents.
    - Sorting with the comparator will give us an array such that it can be divided into 
      consecutive groups of [x, x - 1, ....], [y, y - 1, y - 2....], ...
    - There are no two consecutive groups of size 1
    - Each consecutive group's size is at most log N + 1.
*/
int done[1001][1001];
inline bool ask(int a, int b)
{
    bool ret = 0;
    if (a > b) {swap(a, b); ret = 1;}
    if (done[a][b] == -1) done[a][b] = Query(a, b);
    return ret ^ done[a][b];
}
int n, P[1001], A[1001];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

monster.cpp: In function 'void mergeSort(int, int)':
monster.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int M = L + R >> 1;
      |                 ~~^~~

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