Submission #419646

#	Time	Username	Problem	Language	Result	Execution time	Memory
419646		alishahali1382	Monster Game (JOI21_monster)	C++17	93 / 100	134 ms	4532 KiB

monster

#include "monster.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<" "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<" ";cerr<<"\n";}
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) return cout<<x<<"\n", 0;
#define SZ(x) ((int)x.size())

const int inf=1000010000;
const int mod=1000000007;
const int MAXN=1010;

int n, m, q, k, u, v, x, y, t, l, r, ans;
int A[MAXN][MAXN];
int P[MAXN], deg[MAXN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

bool Ask(int u, int v){
	if (u==v) return 0; // wtf
	if (u>v) return !Ask(v, u);
	if (A[u][v]==-1) A[u][v]=!Query(u, v);
	return A[u][v];
}
vi FUCK(vi A){
	vi B(n, 0);
	for (int i=0; i<n; i++) B[A[i]]=i;
	return B;
}

void MergeSort(int *l, int *r){
	if (r-l<=1) return ;
	int *mid=(r-l)/2+l;
	MergeSort(l, mid);
	MergeSort(mid, r);
	vector<int> vec(r-l, 0);
	merge(l, mid, mid, r, vec.begin(), Ask);
	for (int i=0; i<r-l; i++) (*(l+i))=vec[i];
}

vi Solve(int _n){
	n=_n;
	memset(A, -1, sizeof(A));
	vi out;
	iota(P, P+n, 0);
	shuffle(P, P+n, rng);
	MergeSort(P, P+n);
	// cerr<<"P: ";for (int i=0; i<n; i++) cerr<<P[i]<<" \n"[i==n-1];

	int t=0, y=P[n-1];
	for (int i=0; i<n; i++) if (i!=y) t+=Ask(y, i);
	if (t==n-2){
		if (Ask(P[2], P[0])){
			for (int i=n-1; ~i; i--) out.pb(P[i]);
		}
		else{
			out.pb(P[0]);
			for (int i=n-1; i; i--) out.pb(P[i]);
		}
		// debugv(out)
		// debug("shit")
		return FUCK(out);
	}
	int j=0, pos=n-1;
	for (int i=0; i<n-1; i++) if (Ask(y, P[i])){
		x=P[i];
		j=i;
		break ;
	}
	if (t==1){
		int tx=0;
		for (int i=n-1; ~i && tx<=1; i--) if (P[i]!=x) tx+=Ask(x, P[i]);
		if (tx==1){
			out.pb(P[pos--]);
		}
		else{
			out.pb(P[pos--]);
			out.pb(P[pos--]);
			assert(tx<=n-2);
		}
	}
	else{
		out.pb(P[pos--]);
		out.pb(P[pos--]);
		while (~pos && P[pos]!=x && Ask(y, P[pos])) out.pb(P[pos--]);
	}
	reverse(all(out));
	// debugv(out)

	int last=P[n-1];
	while (~pos){
		int nw=P[pos];
		vi shit;
		while (1){
			int v=P[pos--];
			shit.pb(v);
			if (Ask(last, v)) break ;
		}
		reverse(all(shit));
		for (int x:shit) out.pb(x);
		last=nw;
	}
	reverse(all(out));
	return FUCK(out);
}

Compilation message (stderr)

monster.cpp: In function 'vi Solve(int)':
monster.cpp:74:6: warning: variable 'j' set but not used [-Wunused-but-set-variable]
   74 |  int j=0, pos=n-1;
      |      ^

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