oj.uz

Submission #497222

# Submission time Handle Problem Language Result Execution time Memory
497222 2021-12-22T18:42:34 Z inksamurai Slagalica (COCI19_slagalica2) C++17
70 / 70
 38 ms 2740 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define crep(i,x,n) for(int i=x;i<n;i++)
#define drep(i,n) for(int i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _32bB6rn ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define nare {cout<<"-1\n"; exit(0);}
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<int,int>;
using vi=vector<int>;

int main(){
_32bB6rn;
	int n;
	cin>>n;
	vec(vi) rbts(8);
	rep(i,n){
		int x,y;
		cin>>x>>y;
		x--;
		rbts[x].pb(y);
	}
	rep(i,8){
		sort(rbts[i].rbegin(),rbts[i].rend());
	}
	int open=sz(rbts[4])?4:5;
	int close=sz(rbts[6])?6:7;
	if(sz(rbts[4])>1 
		or sz(rbts[5])>1 
		or (sz(rbts[4]) and sz(rbts[5]))){
			nare;
	}
	if(sz(rbts[6])>1 
		or sz(rbts[7])>1 
		or (sz(rbts[6]) and sz(rbts[7]))){
		nare;
	}
	if(open==4){
		if(close==6){
			if(sz(rbts[3])!=sz(rbts[0])+1) nare;
		}else{
			if(sz(rbts[3])!=sz(rbts[0])) nare;
		}
	}else{
		if(close==6){
			if(sz(rbts[3])!=sz(rbts[0])) nare;
		}else{
			if(sz(rbts[3])+1!=sz(rbts[0])) nare;
		}
	}
	vec(pii) pans;
	pans.pb({rbts[open][0],open});
	int now=(open==4?1:0);
	while(sz(rbts[3]) or sz(rbts[0])){
		if(now){
			if(!sz(rbts[3])) nare;
			while(sz(rbts[2]) and rbts[2].back()<rbts[3].back()){
				pans.pb({rbts[2].back(),2});
				rbts[2].pop_back();
			}
			pans.pb({rbts[3].back(),3});
			rbts[3].pop_back();
		}else{
			if(!sz(rbts[0])) nare;
			while(sz(rbts[1]) and rbts[1].back()<rbts[0].back()){
				pans.pb({rbts[1].back(),1});
				rbts[1].pop_back();
			}
			pans.pb({rbts[0].back(),0});
			rbts[0].pop_back();
		}
		now^=1;
	}
	auto affine=[&](int id,vi rbt){
		vec(pii) delay;
		while(sz(pans)>id+1){
			delay.pb(pans.back());
			pans.pop_back();
		}
		while(sz(rbt)){
			pans.pb({rbt.back(),11});
			rbt.pop_back();
		}
		while(sz(delay)){
			pans.pb(delay.back());
			delay.pop_back();
		}
	};
	if(sz(rbts[2])){
		int id=-1;
		rep(i,sz(pans)){
			if(pans[i].se==4 or pans[i].se==0 or pans[i].se==2){
				id=i;
			}
		}
		if(id==-1) nare;
		affine(id,rbts[2]);
	}
	if(sz(rbts[1])){
		int id=-1;
		rep(i,sz(pans)){
			if(pans[i].se==5 or pans[i].se==3 or pans[i].se==1){
				id=i;
			}
		}
		if(id==-1) nare;
		affine(id,rbts[1]);
	}
	pans.pb({rbts[close][0],close});
	for(auto p : pans){
		cout<<p.fi<<" ";
	}
//	
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 1 ms 312 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 2420 KB Output is correct
2 Correct 19 ms 876 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2196 KB Output is correct
2 Correct 18 ms 832 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 876 KB Output is correct
2 Correct 33 ms 2392 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 824 KB Output is correct
2 Correct 31 ms 2232 KB Output is correct
3 Correct 32 ms 2700 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2392 KB Output is correct
2 Correct 19 ms 1836 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2372 KB Output is correct
2 Correct 20 ms 832 KB Output is correct
3 Correct 29 ms 2452 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 924 KB Output is correct
2 Correct 26 ms 2344 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2740 KB Output is correct
2 Correct 25 ms 1724 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2268 KB Output is correct
2 Correct 18 ms 1732 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2608 KB Output is correct
2 Correct 21 ms 1928 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2364 KB Output is correct
2 Correct 19 ms 1852 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2384 KB Output is correct
2 Correct 20 ms 1792 KB Output is correct