Submission #444686

#	Time	Username	Problem	Language	Result	Execution time	Memory
444686		penguinhacker	Slagalica (COCI19_slagalica2)	C++14	15 / 70	36 ms	3004 KiB

slagalica

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

#define ll long long
#define ar array

const int mxN=1e5;
int n;
ar<int, 2> a[mxN];
vector<ar<int, 2>> first, last; // 0 is sticking out
deque<int> q[2][2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=0; i<n; ++i) {
		int x, y;
		cin >> x >> y;
		if (x==5||x==6)
			first.push_back({y, x-5});
		else if (x==7||x==8)
			last.push_back({y, (x-7)^1});
		else if (x==3||x==4)
			q[0][x==4].push_back(y);
		else
			q[1][x==2].push_back(y);
	}
	if (first.size()!=1||last.size()!=1) {
		cout << -1;
		return 0;
	}
	for (int i : {0, 1})
		for (int j : {0, 1})
			sort(q[i][j].begin(), q[i][j].end());
	vector<int> ans={first[0][0]};
	int cur=first[0][1];
	for (int i=1; i<n-1; ++i) {
		if (q[cur][0].empty()&&q[cur][1].empty()) {
			cout << -1;
			return 0;
		}
		int t;
		if (q[cur][0].empty()^q[cur][1].empty())
			t=q[cur][0].empty();
		else if (q[0][last[0][1]].size()+q[1][last[0][1]].size()>1)
			t=q[cur][1][0]<q[cur][0][0];
		else
			t=last[0][1]^1;
		assert(q[cur][t].size());
		ans.push_back(q[cur][t][0]);
		q[cur][t].pop_front();
		cur=t;
	}
	if (cur!=last[0][1]) {
		cout << -1;
	} else {
		for (int i : ans)
			cout << i << " ";
		cout << last[0][0];
	}
	return 0;
}

• Subtask 1: 5 / 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