This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define double long double
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define OUTIE true
#define INNIE false
using namespace std;
using ll = long long;
template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};
typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
constexpr int MAX_N = 1E5 + 5;
bool flag, last;
int N, X[MAX_N], A[MAX_N];
signed leftOutie, rightOutie, leftInnie, rightInnie, result[MAX_N];
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pieces[2][2];
signed main() {
#ifdef LOCAL
freopen("input.INP", "r", stdin);
#endif // LOCAL
cin.tie(0) -> sync_with_stdio(0);
cout.tie(0);
cin >> N;
fort(i, 1, N) {
cin >> X[i] >> A[i];
if (X[i] == 1) {
pieces[OUTIE][OUTIE].emplace(A[i], i);
++leftOutie;
++rightOutie;
} else if (X[i] == 2) {
pieces[OUTIE][INNIE].emplace(A[i], i);
++leftOutie;
++rightInnie;
} else if (X[i] == 3) {
pieces[INNIE][OUTIE].emplace(A[i], i);
++leftInnie;
++rightOutie;
} else if (X[i] == 4) {
pieces[INNIE][INNIE].emplace(A[i], i);
++leftInnie;
++rightInnie;
} else if (X[i] == 5) {
result[1] = A[i];
++rightOutie;
flag = OUTIE;
} else if (X[i] == 6) {
result[1] = A[i];
++rightInnie;
flag = INNIE;
} else if (X[i] == 7) {
result[N] = A[i];
++leftOutie;
last = OUTIE;
} else if (X[i] == 8) {
result[N] = A[i];
++leftInnie;
last = INNIE;
}
}
if (rightOutie != leftInnie || rightInnie != leftOutie) {
cout << -1 << '\n';
return 0;
}
fore(i, 2, N) {
const bool x = !flag;
int which = -1, what = -1;
if (flag == OUTIE)
--rightOutie;
else
--rightInnie;
if (x == OUTIE)
--leftOutie;
else
--leftInnie;
fort(y, 0, 1) {
if (pieces[x][y].empty() ||
i + 1 < N && (y == OUTIE && last == INNIE && rightOutie == 1 ||
y == INNIE && last == OUTIE && rightInnie == 1))
continue;
const auto &[a, it] = pieces[x][y].top();
if (which < 0 || A[which] > a) {
which = it;
what = y;
}
}
if (which < 0) {
cout << -1 << '\n';
return 0;
}
result[i] = A[which];
pieces[x][what].pop();
}
fort(i, 1, N)
cout << result[i] << ' ';
cout << '\n';
return 0;
}
Compilation message (stderr)
slagalica.cpp: In function 'int main()':
slagalica.cpp:131:59: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
131 | i + 1 < N && (y == OUTIE && last == INNIE && rightOutie == 1 ||
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
slagalica.cpp:131:27: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
131 | i + 1 < N && (y == OUTIE && last == INNIE && rightOutie == 1 ||
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
132 | y == INNIE && last == OUTIE && rightInnie == 1))
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
slagalica.cpp:130:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
130 | if (pieces[x][y].empty() ||
| ^~
slagalica.cpp:134:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
134 | const auto &[a, it] = pieces[x][y].top();
| ^~~~~
# | 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... |