oj.uz

Submission #527562

# Submission time Handle Problem Language Result Execution time Memory
527562 2022-02-17T16:19:00 Z jamielim On the Grid (FXCUP4_grid) C++17
0 / 100
 1 ms 300 KB 
#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
			
		}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] is the child's index
					ans[test[b]]=cur-n+b+1;
					rev[ans[test[b]]-1]=test[b];
					bool move=0;
					for(int i=0;i<SZ(rem)-1;i++){
						if(move)rem[i]=rem[i+1];
						else if(rem[i]==test[b]){
							move=1;
							rem[i]=rem[i+1];
						}
					}
					rem.pop_back();
					break;
				}
			}
		}
		prv=cur;
	}
	return ans;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 300 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -