Submission #420063

#	Time	Username	Problem	Language	Result	Execution time	Memory
420063		oolimry	Monster Game (JOI21_monster)	C++17	100 / 100	143 ms	1548 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
typedef long long lint;
typedef pair<lint,lint> ii;

map<ii, int> M;
bool query(int a, int b){
	if(M.find(ii(a,b)) != M.end()) return M[ii(a,b)];
	int res = Query(a,b);
	//show3(a,b,res);
	M[ii(a,b)] = res;
	M[ii(b,a)] = not res;
	return res;
}

struct thing{
	int s, e, c;
};

vector<int> Solve(int n) {
	vector<int> T(0);
	vector<int> A(n);
	vector<int> B(n);
	//for (int i = 0; i < n; i++) T[i] = i;
	for (int i = 0; i < n; i++) A[i] = 0;
	for (int i = 0; i < n; i++) B[i] = 0;
	int seed = time(0);
	//srand(1622964658);
	srand(1622968914);
	
	T.push_back(0);
	for(int i = 1;i < n;i++){
		int low = -1, high = sz(T);
		while(low != high-1){
			int mid = (low+high)/2;
			if(query(T[mid], i)) high = mid;
			else low = mid;
		} 
		T.insert(T.begin()+low+1, i);
		
	}
	
	//cerr << "------------" << endl;
	
	//cerr << "------------" << endl;
	int a = 0;
	bool awins = false;
	vector<thing> ranges;
	for(int i = 1;i < n;i++){
		if(i <= a+1) continue;
		//show2(a,i)
		if(i == a+2) awins = query(T[a], T[i]);
		else{
			if(awins){
				if(not query(T[a], T[i])){
					if(i-1 == a+2){
						ranges.push_back({a,i-1,2});
					}
					else{
						ranges.push_back({a,i-1,1});
					}
					a = i;
				}
			}
			else{
				if(query(T[a], T[i])){
					ranges.push_back({a,i,2});
					a = i+1;
				}
			}
		}
	}
	
	if(a != n) ranges.push_back({a,n-1,1});
	
	int zero = -1;
	if(ranges[0].e != 2){
		///solve range 0;
		int e = ranges[0].e;
		int x = e;
		
		int cnt = 0;
		int e2 = ranges[0].e;
		if(sz(ranges) > 1) e2 = ranges[1].e;
		
		for(int i = 0;i <= e2;i++){
			if(i == x) continue;
			if(query(T[x], T[i])) cnt++;
		}
		
		if(ranges[0].c == 2){
			if(cnt == 1) zero = 0;
			else zero = 1;
		}
		else{
			if(cnt == 1) zero = e;
			else zero = e-1;
		}
	}
	else{
		int x = 0;
		while(x < 2){
			int cnt = 0;
			int e2 = ranges[0].e;
			if(sz(ranges) > 1) e2 = ranges[1].e;
			
			for(int i = 0;i <= e2;i++){
				if(i == x) continue;
				if(query(T[x], T[i])) cnt++;
			}
			
			if(cnt != 1){
				break;
			}
			x++;
		}
		zero = (x+2)%3;
	}
	//show(zero);
	for(int i = 0;i <= ranges[0].e;i++){
		A[i] = T[(zero-i+ranges[0].e+1)%(ranges[0].e+1)];
	}
	
	for(int rno = 1;rno < sz(ranges);rno++){
		int s = ranges[rno].s; int e = ranges[rno].e;
		int z = s;
		int L = (e-s+1);
		for(int i = 0;i < L;i++){
			if(query(A[s-1],T[i+s])){
				z = i+s;
				break;
			}
			if(query(A[s-1],T[e-i])){
				z = e-i;
				break;
			}
		}
		//show(z);
		for(int i = 0;i < L;i++){
			A[i+s] = T[(z-i-s+L+L)%L+s];
		}
	}
	
	for(int i = 0;i < n;i++) B[A[i]] = i;
	//cerr << "------------" << endl;

	return B;
}

Compilation message (stderr)

monster.cpp: In function 'std::vector<int> Solve(int)':
monster.cpp:33:6: warning: unused variable 'seed' [-Wunused-variable]
   33 |  int seed = time(0);
      |      ^~~~

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