Submission #147997

#	Time	Username	Problem	Language	Result	Execution time	Memory
147997		imsifile	On the Grid (FXCUP4_grid)	C++17	0 / 100	2 ms	376 KiB

grid

#include "grid.h"
#include <vector>
#include <stdio.h>
using namespace std;
 
int N, sm[1010], rcn, rot[1010], rvd[1010], chk[1010]; // rvd[i]: disk number of size i
int Put(){
	vector<int> v;
	for(int i=1; i<=N; i++) v.push_back(sm[i]);
	return PutDisks(v)-N;
}
 
void fill(){
	for(int i=0; i<rcn; i++) sm[i+1]=rot[i];
	for(int i=rcn, j=1; j<=N; j++){
		if(chk[j]) sm[++i]=rvd[j];
	}
}
 
std::vector<int> SortDisks(int N_) {
	rcn = N = N_;
	for(int i=0; i<N; i++) rot[i]=i+1;
 
	fill();
	int ini=Put(), nxt;
	while(ini && rcn>1){
		int tmp=rot[rcn-1];
		for(int i=rcn-1; i>=0; i--) rot[i+1]=rot[i];
		rot[0]=tmp;
		fill(); nxt=Put();
		if(nxt >= ini){
			rcn--;
			rvd[1+nxt]=rot[0], chk[1+nxt]=1;
			for(int i=0; i<rcn; i++) rot[i]=rot[i+1];
		}
		else ini=nxt;
	}
 
	for(int i=1, j=0; i<=N; i++){
		if(chk[i]) sm[rvd[i]]=i;
		else sm[rot[j++]]=i;
	}
	std::vector<int> dap;
	for(int i=1; i<=N; i++) dap.push_back(sm[i]);
	return dap;
}

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