Submission #1264580

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264580		goulthen	Slagalica (COCI19_slagalica2)	C++20	10 / 70	22 ms	3020 KiB

slagalica

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define per(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define fi first
#define se second

const int MAXN = 1e5 + 10;
const int INF = 1e18+10;
vector<int> g[9], val[9];
pair<int,int> sh[9];
int cl=0,cr=0,cll=0,crr=0;

void update(int tp, int delta = 1) {
	if (sh[tp].fi == 0) cl+=delta;
	else if(sh[tp].fi == 1) cll+=delta;
	if (sh[tp].se == 0) cr+=delta;
	else if (sh[tp].se==1) crr+=delta;
}

bool dfs(int u, vector<int> &path) {
	int bv=0;

	update(u,-1);

	path.pb(val[u].back());
	val[u].pop_back();


	if (u>=7) return 1;

	rep(v,1,8) {
		if(sh[u].se == sh[v].fi || sh[v].fi == -1 || val[v].empty()) continue;
		update(v,-1);
		if(cl+cll+cr+crr >= 2 && ((sh[v].se==0 && cll==0) || (sh[v].se == 1 && cl == 0))) {
			update(v,1);
			continue;
		}
		update(v,1);


		if (val[bv].back() > val[v].back()) bv = v;
	}
	if (bv == 0) return 0;
	return dfs(bv,path);
}

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin >> n;

	rep(i,1,8) {
		sh[i].fi = ((i-1)>>1)&1;
		sh[i].se = (i-1)&1;
	}
	sh[5].fi = sh[6].fi = -1;
	sh[7].se = sh[8].se = -1;
	sh[7].fi = 0;
	val[0].pb(INF);

	int st;
	rep(i,1,n) {
		int tp, v;cin >> tp >> v;
		val[tp].pb(v + (tp >= 7 ? (int)1e9 : 0));
		if (tp==5 || tp == 6) st = tp;

		if (tp > 6) continue;
		update(tp);
	}
	rep(i,1,8) sort(val[i].begin(), val[i].end(), greater<int>());

	vector<int> ans;
	if(!dfs(st, ans)) {
		cout << "-1\n";
		return 0;
	}

	for (int &v : ans) cout << v%((int)1e9) << ' ';
	cout << '\n';

	return 0;
}

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