Submission #1148986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148986		Darren0724	Monster Game (JOI21_monster)	C++17	72 / 100	30 ms	1012 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
using namespace std;
const int N=1005;
int n;
map<pair<int,int>,int> m;
vector<int> r;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
inline int ask(int a,int b){
	if(m.find({a,b})!=m.end()){
		return m[{a,b}];
	}
	if(m.find({b,a})!=m.end()){
		return m[{b,a}]^1;
	}
	return m[{a,b}]=Query(r[a],r[b]);
}
vector<int> dc(int l,int r){\
	if(r-l==1){
		return vector<int>(1,l);
	}
	int m=(l+r)>>1;
	vector<int> a = dc(l,m);
	vector<int> b = dc(m,r);
	vector<int> c;
	int j=0;
	int sz=b.size();
	for(int i:a){
		while(j<sz&&ask(i,b[j])){
			c.push_back(b[j]);
			j++;
		}
		c.push_back(i);
	}
	while(j<sz){
		c.push_back(b[j]);
		j++;
	}
	return c;
}
vector<int> Solve(int n1) {
	n=n1;
  r.resize(n);
  iota(r.begin(),r.end(),0);
  shuffle(r.begin(),r.end(),rnd);
	vector<int> v = dc(0,n);
	vector<int> ans(n),t(n);
	int cnt=0;
	for(int i=0;i<n-1;i++){
		cnt+=ask(v[n-1],v[i]);
    //cout<<ask(v[n-1],v[i])<<endl;
	}
  //cout<<cnt<<endl;

	int i=n-1;
	for(;cnt<n;cnt++,i--){
		t[i]=cnt;
	}
	int last=n-1;
	while(i>=0){
		int rec=i;
		while(!ask(v[i],v[last])){
			i--;
		}
    //cout<<"i:"<<i<<endl;
		last=rec;
		cnt=rec;
		for(int j=i;j<=rec;j++){
			t[j]=cnt;
			cnt--;
		}
		i--;
	}
	for(int i=0;i<n;i++){
		ans[r[v[i]]]=t[i];
	}
	
	return ans;
}
/*
9
1 5 2 0 8 6 3 4 7
*/

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