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 <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
pii change[9];
int n;
vector<int> type[9];
void makeChange() {
change[1] = pii(1,1);
change[2] = pii(1,2);
change[3] = pii(2,1);
change[4] = pii(2,2);
change[5] = pii(0,1);
change[6] = pii(0,2);
change[7] = pii(1,0);
change[8] = pii(2,0);
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n;
makeChange();
for (int i = 1; i <= n; i++) {
int t,id;
cin >> t >> id;
type[t].push_back(id);
}
for (int i = 1; i <= 4; i++) sort(type[i].begin(),type[i].end(),greater<int> {});
int st = (type[5].empty()) ? 6: 5;
int fin = (type[7].empty()) ? 8: 7;
vector<pii> res;
res.push_back(pii(st,type[st].back()));
bool found = 1;
int pre = change[st].second;
while (found) {
int id;
if (pre == 1) {
if (type[3].empty() && type[4].empty()) found = 0;
else if (type[3].empty() || (!type[4].empty() && type[4].back() < type[3].back())) {
res.push_back(pii(4,type[4].back()));
type[4].pop_back();
id = 4;
} else {
res.push_back(pii(3,type[3].back()));
type[3].pop_back();
id = 3;
}
} else {
if (type[1].empty() && type[2].empty()) found = 0;
else if (type[1].empty() || (!type[2].empty() && type[2].back() < type[1].back())) {
res.push_back(pii(2,type[2].back()));
type[2].pop_back();
id = 2;
} else {
res.push_back(pii(1,type[1].back()));
type[1].pop_back();
id = 1;
}
}
if (found) pre = change[id].second;
}
// assert(!res.empty());
if (change[res.back().first].second == change[fin].first) {
cout << -1;
return 0;
}
if (!type[1].empty()) {
cout << -1;
return 0;
}
if (!type[4].empty()) {
cout << -1;
return 0;
}
int id;
if (type[2].empty() && type[3].empty()) {
res.push_back(pii(fin,type[fin].back()));
for (pii i: res) cout << i.second << ' ';
return 0;
} else id = (type[2].empty()) ? 3: 2;
int pos = -1;
for (int i = res.size() - 1; i >= 0; i--) {
if (change[res[i].first].second != change[id].first) {
pos = i;
break;
}
}
assert(pos != -1);
for (int i = 0; i <= pos; i++) cout << res[i].second << ' ';
for (int i = type[id].size() - 1; i >= 0; i--) cout << type[id][i] << ' ';
res.push_back(pii(fin,type[fin].back()));
for (int i = pos+1; i < (int) res.size(); i++) cout << res[i].second << ' ';
return 0;
}
# | 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... |