oj.uz

Submission #229223

# Submission time Handle Problem Language Result Execution time Memory
229223 2020-05-03T21:12:44 Z VEGAnn Slagalica (COCI19_slagalica2) C++14
70 / 70
 45 ms 3572 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 3100 KB Output is correct
2 Correct 32 ms 1984 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3000 KB Output is correct
2 Correct 29 ms 1916 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2044 KB Output is correct
2 Correct 40 ms 3088 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 1920 KB Output is correct
2 Correct 37 ms 2932 KB Output is correct
3 Correct 44 ms 3420 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3056 KB Output is correct
2 Correct 31 ms 2012 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2932 KB Output is correct
2 Correct 31 ms 1916 KB Output is correct
3 Correct 42 ms 3344 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 2048 KB Output is correct
2 Correct 41 ms 3124 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3572 KB Output is correct
2 Correct 30 ms 1792 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3104 KB Output is correct
2 Correct 29 ms 1920 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 3440 KB Output is correct
2 Correct 35 ms 2048 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3064 KB Output is correct
2 Correct 29 ms 1920 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3056 KB Output is correct
2 Correct 30 ms 1920 KB Output is correct