This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// #define _FORTIFY_SOURCE 0
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("unroll-loops")
// //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
// #pragma GCC optimize("inline")
// #pragma GCC optimize("-fgcse")
// #pragma GCC optimize("-fgcse-lm")
// #pragma GCC optimize("-fipa-sra")
// #pragma GCC optimize("-ftree-pre")
// #pragma GCC optimize("-ftree-vrp")
// #pragma GCC optimize("-fpeephole2")
// #pragma GCC optimize("-ffast-math")
// #pragma GCC optimize("-fsched-spec")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC optimize("-falign-jumps")
// #pragma GCC optimize("-falign-loops")
// #pragma GCC optimize("-falign-labels")
// #pragma GCC optimize("-fdevirtualize")
// #pragma GCC optimize("-fcaller-saves")
// #pragma GCC optimize("-fcrossjumping")
// #pragma GCC optimize("-fthread-jumps")
// #pragma GCC optimize("-funroll-loops")
// #pragma GCC optimize("-fwhole-program")
// #pragma GCC optimize("-freorder-blocks")
// #pragma GCC optimize("-fschedule-insns")
// #pragma GCC optimize("inline-functions")
// #pragma GCC optimize("-ftree-tail-merge")
// #pragma GCC optimize("-fschedule-insns2")
// #pragma GCC optimize("-fstrict-aliasing")
// #pragma GCC optimize("-fstrict-overflow")
// #pragma GCC optimize("-falign-functions")
// #pragma GCC optimize("-fcse-skip-blocks")
// #pragma GCC optimize("-fcse-follow-jumps")
// #pragma GCC optimize("-fsched-interblock")
// #pragma GCC optimize("-fpartial-inlining")
// #pragma GCC optimize("no-stack-protector")
// #pragma GCC optimize("-freorder-functions")
// #pragma GCC optimize("-findirect-inlining")
// #pragma GCC optimize("-fhoist-adjacent-loads")
// #pragma GCC optimize("-frerun-cse-after-loop")
// #pragma GCC optimize("inline-small-functions")
// #pragma GCC optimize("-finline-small-functions")
// #pragma GCC optimize("-ftree-switch-conversion")
// #pragma GCC optimize("-foptimize-sibling-calls")
// #pragma GCC optimize("-fexpensive-optimizations")
// #pragma GCC optimize("-funsafe-loop-optimizations")
// #pragma GCC optimize("inline-functions-called-once")
// #pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
#define base complex<ld>
using namespace std;
const ll INF = (ll)2e9;
const ll inf = (ll)1e18;
const ld eps = (ld)1e-12;
const ll mod = (ll)1e9 + 7;
const ll p = 31;
const ll mod2 = (ll)1e9 + 7;
const ll MAXN = (ll)1000 + 3;
const ll MAXC = (ll)1e6 + 11;
const ll MAXE = (ll)100;
const ll MAXLOG = (ll)19;
const ll asci = (ll)256;
const ll block = 31623;
const ld PI = acos(-1LL);
const ld e = 2.7182818284;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<
// pii,
// null_type,
// less<pii>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;
ll int_rand() {
if (RAND_MAX == (1LL << 15) - 1LL) {
return (rand() << 15) + rand();
}
return rand();
}
ll ll_rand() {
return ((ll)int_rand() << 30LL) + int_rand();
}
istream& operator >>(istream &in, pii &x) {
cin >> x.first >> x.second;
return in;
}
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
for (T &cnt : arr) {
in >> cnt;
}
return in;
}
bool can_do(vi puzzle, int st, int end) {
if (st == 0 && end == 0) {
if (puzzle[0] == puzzle[3]) {
if (puzzle[2] && !puzzle[0]) return 0;
return 1;
}
return 0;
}
if (st == 0 && end == 1) {
if (puzzle[0] - puzzle[3] == 1) return 1;
return 0;
}
if (st == 1 && end == 0) {
if (puzzle[3] - puzzle[0] == 1) return 1;
return 0;
}
if (st == 1 && end == 1) {
if (puzzle[0] == puzzle[3]) {
if (puzzle[1] && !puzzle[3]) return 0;
return 1;
}
return 0;
}
return 0;
}
void solve() {
int n; cin >> n;
vector<deque<int>> a(8);
for (int i = 0; i < n; ++i) {
int x, c; cin >> x >> c;
a[x - 1].push_back(c);
}
if (a[4].size() + a[5].size() != 1) {
cout << "-1\n";
return;
}
if (a[6].size() + a[7].size() != 1) {
cout << "-1\n";
return;
}
vi ind(2);
vi ans(n);
vi puzzle(4);
for (int i = 0; i < 4; ++i) {
sort(all(a[i]));
puzzle[i] = a[i].size();
}
for (int i = 4; i < 8; ++i) {
if (a[i].size()) {
ind[(i & 2) >> 1] = (i & 1) ^ ((i & 2) >> 1) ^ 1;
if ((i & 2) >> 1) ans[n - 1] = a[i][0];
else ans[0] = a[i][0];
a[i].pop_back();
}
}
if (!can_do(puzzle, ind[0], ind[1])) {
cout << "-1\n";
return;
}
for (int i = 1; i < n - 1; ++i) {
vector<pii> fin;
for (int j = 0; j < 4; ++j) if (a[j].size()) fin.push_back(mp(a[j].front(), j));
sort(all(fin));
for (int j = 0; j < fin.size(); ++j) {
if (((fin[j].second & 2) >> 1) == ind[0]) {
puzzle[fin[j].second]--;
if (can_do(puzzle, (fin[j].second & 1) ^ 1, ind[1])) {
ind[0] = (fin[j].second & 1) ^ 1;
ans[i] = a[fin[j].second].front();
a[fin[j].second].pop_front();
break;
}
puzzle[fin[j].second]++;
}
}
}
for (int i : ans) cout << i << " ";
}
signed main() {
srand(time(0LL));
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#endif
cout.precision(30);
solve();
return 0LL;
}
Compilation message (stderr)
slagalica.cpp: In function 'void solve()':
slagalica.cpp:184:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
184 | for (int j = 0; j < fin.size(); ++j) {
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |