Submission #527564

#	Time	Username	Problem	Language	Result	Execution time	Memory
527564		jamielim	On the Grid (FXCUP4_grid)	C++17	0 / 100	1 ms	204 KiB

grid

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

#define pb emplace_back
#define SZ(x) (int)x.size()

vector<int> SortDisks(int n) {
	vector<int> rem; // remaining child indices
	vector<int> ans; // length for i-th child
	int rev[n]; // inverse map of ans (child with length i-1)
	for(int i=0;i<n;i++){
		rem.pb(i);
		ans.pb(-1);
		rev[i]=-1;
	}
	int prv=PutDisks(rem);
	while(!rem.empty()){
		vector<int> test;
		int tmp=rem[SZ(rem)-1];
		for(int i=0;i<SZ(rem);i++){
			swap(tmp,rem[i]); // rightshift everything
		}
		int idx=0;
		for(int i=0;i<n;i++){
			if(rev[i]==-1)test.pb(rem[idx++]); // there is no known child with this length
			else test.pb(rev[i]); // there is a known child with this length -> we want to un-bottleneck
		}
		int cur=PutDisks(test);
		if(cur==prv-1){ // moving the top unknown to the bottom didnt change anything
			prv=cur;
		}else{ // the bottom ("length" (index in test) whose child is unknown) child can be determined
			for(int b=0;b<n;b++){
				if(rev[b]==-1){
					// test[b]=rem[0] is the child's index
					ans[rem[0]]=cur-n+b+1;
					rev[ans[rem[0]]-1]=rem[0];
					for(int i=0;i<SZ(rem)-1;i++){
						rem[i]=rem[i+1];
					}
					rem.pop_back();
					break;
				}
			}
		}
	}
	return ans;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 31
• Subtask 3: 0 / 57