Submission #420058

#	Time	Username	Problem	Language	Result	Execution time	Memory
420058		errorgorn	Monster Game (JOI21_monster)	C++17	85 / 100	231 ms	292 KiB

monster

#include "monster.h"

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

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);(s<e?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

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

namespace {
	int n;
}  // namespace

std::vector<int> Solve(int N) {
	n=N;
	
	vector<int> v;
	rep(x,0,n) v.pub(x);
	
	stable_sort(all(v),[](int i,int j){
		return !Query(i,j);
	});
	
	//for (auto &it:v) cout<<it<<" "; cout<<endl;
	
	vector<int> vv;
	rep(x,1,n) if (Query(v[0],v[x])) vv.pub(v[x]);
	
	int l=0,r;
	
	if (sz(vv)!=1) r=sz(vv);
	else{
		//if its 1: we found 2
		//if its 0: we found 1
		
		int curr=0;
		//cout<<vv[0]<<endl;
		rep(x,0,n) if (x!=vv[0]) curr+=Query(vv[0],x);
		if (curr==2) r=1;
		else r=0;
	}
	
	vector<int> rank,ans(n,0);
	
	while (true){
		rep(x,r+1,l) rank.pub(v[x]);
		
		if (r==n-1) break;
		
		rep(x,r+1,n) if (Query(v[l],v[x])){
			l=r+1,r=x;
			break;
		}
	}
	
	rep(x,0,n) ans[rank[x]]=x;
	
	return ans;
}

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