Submission #559966

#	Time	Username	Problem	Language	Result	Execution time	Memory
559966		minhcool	Monster Game (JOI21_monster)	C++17	10 / 100	199 ms	1856 KiB

monster

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

//#define int long long
#define fi first
#define se second
#define pb push_back
//#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e5 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, a[N];

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int rnd(int l, int r){
	int temp = rng() % (r - l + 1);
	temp = (temp + (r - l + 1)) % (r - l + 1);
	return temp + l;
}

vector<int> er(vector<int> a, int x){
	vector<int> b;
	for(auto it : a) if(it != x) b.pb(it);
	return b;
}

int deg[N];

map<ii, bool> mp;

void solve_brute(vector<int> x, int l, int r){
	if(x.size() == 1){
		a[x[0]] = l;
		return;
	}
	assert(x.size() != 3);
	for(int i = 0; i < x.size(); i++){
		for(int j = i + 1; j < x.size(); j++){
			mp[{x[i], x[j]}] = Query(x[i], x[j]);
			if(mp[{x[i], x[j]}]) deg[x[i]]++;
			else deg[x[j]]++;
		}
	}
	if(x.size() == 2){
		if(!mp[{x[0], x[1]}]){
			a[x[0]] = r, a[x[1]] = l;
		}
		else{
			a[x[1]] = r, a[x[0]] = l;
		}
		return;
	}
	int mn0 = -1, mn1, mx0 = -1, mx1;
	for(auto it : x){
		if(deg[it] >= 2 && deg[it] <= x.size() - 3){
			a[it] = l + deg[it];
		}
		if(deg[it] == 1){
			if(mn0 == -1) mn0 = it;
			else mn1 = it;
		}
		if(deg[it] == x.size() - 2){
			if(mx0 == -1) mx0 = it;
			else mx1 = it;
		}
	}
	if(mp[{mn0, mn1}]){
		a[mn0] = l; a[mn1] = l + 1;
	}
	else{
		a[mn0] = l + 1; a[mn1] = l;
	}
	if(mp[{mx0, mx1}]){
		a[mx0] = r - 1; a[mx1] = r;
	}
	else{
		a[mx0] = r; a[mx1] = r - 1;
	}
}

void solve(vector<int> x, int l, int r){
	if(x.size() <= 10){
		solve_brute(x, l, r);
		return;
	}
	int temp = x[rnd(0, x.size() - 1)];
	vector<int> vc1, vc2;
	for(auto it : x){
		if(it == temp) continue;
		if(!Query(it, temp)) vc1.pb(it);
		else vc2.pb(it);
	}
	int w1 = vc1[0], w2 = vc2[0];
	for(auto it : vc1){
		if(it == w1) continue;
		if(Query(it, w1)) w1 = it;
	}
	for(auto it : vc2){
		if(it == w2) continue;
		if(Query(w2, it)) w2 = it;
	}
	bool ck1 = 0, ck2 = 0;
	vc1 = er(vc1, w1);
	vc2 = er(vc2, w2);
	
}

vector<int> Solve(int _n){
	n = _n;
	vector<int> temp;
	for(int i = 0; i < n; i++) temp.pb(i);
	solve_brute(temp, 0, n - 1);
	vector<int> temp2;
	for(int i = 0; i < n; i++) temp2.pb(a[i]);
	return temp2;
}

/*
void process(){
	
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}
*/

Compilation message (stderr)

monster.cpp:19:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   19 | const int oo = 1e18 + 7, mod = 1e9 + 7;
      |                ~~~~~^~~
monster.cpp: In function 'void solve_brute(std::vector<int>, int, int)':
monster.cpp:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |  for(int i = 0; i < x.size(); i++){
      |                 ~~^~~~~~~~~~
monster.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |   for(int j = i + 1; j < x.size(); j++){
      |                      ~~^~~~~~~~~~
monster.cpp:65:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   if(deg[it] >= 2 && deg[it] <= x.size() - 3){
      |                      ~~~~~~~~^~~~~~~~~~~~~~~
monster.cpp:72:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   if(deg[it] == x.size() - 2){
      |      ~~~~~~~~^~~~~~~~~~~~~~~
monster.cpp: In function 'void solve(std::vector<int>, int, int)':
monster.cpp:112:7: warning: unused variable 'ck1' [-Wunused-variable]
  112 |  bool ck1 = 0, ck2 = 0;
      |       ^~~
monster.cpp:112:16: warning: unused variable 'ck2' [-Wunused-variable]
  112 |  bool ck1 = 0, ck2 = 0;
      |                ^~~
monster.cpp: In function 'void solve_brute(std::vector<int>, int, int)':
monster.cpp:87:22: warning: 'mx1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |   a[mx0] = r; a[mx1] = r - 1;
      |               ~~~~~~~^~~~~~~
monster.cpp:78:22: warning: 'mn1' may be used uninitialized in this function [-Wmaybe-uninitialized]
   78 |   a[mn0] = l; a[mn1] = l + 1;
      |               ~~~~~~~^~~~~~~

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