Submission #229223

#	Time	Username	Problem	Language	Result	Execution time	Memory
229223		VEGAnn	Slagalica (COCI19_slagalica2)	C++14	70 / 70	45 ms	3572 KiB

slagalica

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define MP make_pair
#define MP3(a, b, c) MP(MP(a, b), c)
#define PB push_back
#define all(x) x.begin(),x.end()
#define pii pair<int, int>
#define piis pair<pii, string>
#define ft first
#define sd second
using namespace std;
const int N = 200100;
vector<int> vc, vec[10];
int n;

void BAD(){
	cout << -1;
	exit(0);
}

int main(){
	
	ios_base::sync_with_stdio(0); cin.tie(0);
	
//	freopen("in.txt","r",stdin); 
	
	cin >> n;
	
	for (int i = 0; i < n; i++){
		int x, v;
		cin >> x >> v;
		vec[x].PB(v);
	}
	
	for (int i = 1; i < 9; i++){
		sort(all(vec[i]));
		reverse(all(vec[i]));
	}
	
	if (sz(vec[5])){
		swap(vec[6], vec[5]);
		swap(vec[7], vec[8]);
		
		swap(vec[2], vec[3]);
		swap(vec[1], vec[4]);
	}
	
	vc.PB(vec[6][0]);
	vec[6].pop_back();
	
	if (sz(vec[8])){
		if (!sz(vec[1]))
			BAD();
		
		if (sz(vec[1]) != sz(vec[4]) + 1)
			BAD();
		
		for (int it = 0; it < n - 2; ){
			if (sz(vec[1]) == 1){
				if (sz(vec[2]) > 0){
					vc.PB(vec[2].back());
					vec[2].pop_back();
				} else {
					vc.PB(vec[1][0]);
					vec[1].pop_back();
				}
				it++;
			} else {
				if (sz(vec[1]) == 0){
					vc.PB(vec[3].back());
					vec[3].pop_back();
					it++;
				} else {
					if (!sz(vec[2]) || (sz(vec[2]) && vec[1].back() < vec[2].back())){
						vc.PB(vec[1].back());
						vec[1].pop_back();
						it++;
						
						while (sz(vec[3]) > 0 && vec[3].back() < vec[4].back()){
							vc.PB(vec[3].back());
							vec[3].pop_back();
							it++;
						}
						
						vc.PB(vec[4].back());
						vec[4].pop_back();
						it++;
					} else {
						vc.PB(vec[2].back());
						vec[2].pop_back();
						it++;
					}
				}
			}
		}
		
		vc.PB(vec[8][0]);
	} else {
		
		if (sz(vec[1]) != sz(vec[4])) 
			BAD();
		
		if (sz(vec[1]) == 0 && sz(vec[3]) > 0)
			BAD();
		
		for (int it = 0; it < n - 2; ){
			if (sz(vec[2]) && (!sz(vec[1]) || (sz(vec[1]) && vec[2].back() < vec[1].back()))){
				vc.PB(vec[2].back());
				vec[2].pop_back();
				it++;
			} else {
				vc.PB(vec[1].back());
				vec[1].pop_back();
				it++;
				
				if (sz(vec[1]) == 0){
					while (sz(vec[3]) > 0){
						vc.PB(vec[3].back());
						vec[3].pop_back();
						it++;
					}
					vc.PB(vec[4].back());
					vec[4].pop_back();
					it++;
					
				} else {
					while (sz(vec[3]) > 0 && vec[3].back() < vec[4].back()){
						vc.PB(vec[3].back());
						vec[3].pop_back();
						it++;
					}
					vc.PB(vec[4].back());
					vec[4].pop_back();
					it++;
				}
			}
		}
		
		vc.PB(vec[7][0]);
	}
	
	for (int x : vc)
		cout << x << " ";
	
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 5 / 5
• Subtask 10: 5 / 5
• Subtask 11: 5 / 5
• Subtask 12: 5 / 5
• Subtask 13: 5 / 5
• Subtask 14: 5 / 5