/*
ID: tmhazem1
LANG: C++14
TASK: pprime
*/
#include <bits/stdc++.h>
using namespace std;
#define S second
#define F first
#define LL long long
const int N = 2e5 + 10;
LL LINF = 100000000000000000;
LL INF = 1000000000;
vector<int>vec[5],ans;
pair<int,int>last;
int nxt[8][2],before[10][2];
int n;
int a[N];
bool bt(int l){
int i = ans.size();
if(ans.back()==INF+10)return 0;
if(i==n-1&&(l==before[last.F][0]||l==before[last.F][1]))return 1;
if(n==2)return (l==5&&last.F==8)||(l==6&&last.F==7);
if(i==n-1)return 0;
int mn = INF+10,nx = 0;
for(int j=0;j<2;j++)
if(vec[nxt[l][j]].back()<mn)mn = vec[nxt[l][j]].back(),nx = j;
if(mn!=INF+10){
ans.push_back(mn);
vec[nxt[l][nx]].pop_back();
if(bt(nxt[l][nx]))return 1;
ans.pop_back();
vec[nxt[l][nx]].push_back(mn);
}
mn = vec[nxt[l][!nx]].back();
if(mn!=INF+10){
ans.push_back(mn);
vec[nxt[l][!nx]].pop_back();
if(bt(nxt[l][!nx]))return 1;
ans.pop_back();
vec[nxt[l][!nx]].push_back(mn);
}
return 0;
}
int main()
{
//freopen("out.txt","w",stdout);
scanf("%d",&n);
nxt[1][0] = nxt[5][0] = nxt[3][0] = 3;
nxt[1][1] = nxt[5][1] = nxt[3][1] = 4;
nxt[2][0] = nxt[6][0] = nxt[4][0] = 2;
nxt[2][1] = nxt[6][1] = nxt[4][1] = 1;
before[7][0] = 2;
before[7][1] = 4;
before[8][0] = 1;
before[8][1] = 3;
int f = 0;
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
if(x==5||x==6)ans.push_back(y),f = x,a[1] = y;
else if(x<5)vec[x].push_back(y);
else last = {x,y};
}
if(n==2){
if((f==5&&last.F==7)||(f==6&&last.F==8)){
puts("-1");return 0;
}
else
printf("%d %d\n",a[1],last.S);
return 0;
}
for(int i=1;i<=4;i++){
vec[i].push_back(INF+10);
sort(vec[i].begin(),vec[i].end(),greater<int>());
}
if(n<=10)
if(!bt(f)){puts("-1");return 0;}
else {
for(auto x:ans)printf("%d ",x);
printf("%d\n",last.S);
return 0;
}
if(vec[4].size()<=2&&vec[1].size()<=2){
int v = min(vec[4].back(),vec[1].back());
int l = f,cnt = 2;
for(int i=vec[nxt[f][0]].size()-1;i>0;i--)
a[cnt++] = vec[nxt[f][0]][i],l = nxt[f][0];
vec[nxt[f][0]].clear();
if(v!=INF+10)a[cnt++] = v,l = vec[4].size()>1?4:1;
f = l;
for(int i=2;i<=3;i++)
if(vec[i].size()>1&&nxt[f][0]!=i){
puts("-1");
return 0;
}
for(int i=vec[nxt[l][0]].size()-1;i>0;i--)
a[cnt++] = vec[nxt[l][0]][i],l = nxt[f][0];
f = l;
if(before[last.F][0]!=f&&before[last.F][1]!=f){
puts("-1");
return 0;
}
a[n] = last.S;
for(int i=1;i<=n;i++)
printf("%d ",a[i]);
puts("");
return 0;
}
if(!bt(f)){puts("-1");return 0;}
else {
for(auto x:ans)printf("%d ",x);
printf("%d\n",last.S);
return 0;
}
}
Compilation message
slagalica.cpp: In function 'int main()':
slagalica.cpp:97:7: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
97 | if(n<=10)
| ^
slagalica.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
62 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
slagalica.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%d%d",&x,&y);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
9832 KB |
Output is correct |
| 2 |
Correct |
34 ms |
9612 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
9496 KB |
Output is correct |
| 2 |
Correct |
40 ms |
9060 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
2312 KB |
Output is correct |
| 2 |
Correct |
37 ms |
3176 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
1940 KB |
Output is correct |
| 2 |
Correct |
35 ms |
2916 KB |
Output is correct |
| 3 |
Correct |
43 ms |
3484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
37 ms |
3068 KB |
Output is correct |
| 2 |
Correct |
31 ms |
2184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
36 ms |
2916 KB |
Output is correct |
| 2 |
Correct |
27 ms |
2152 KB |
Output is correct |
| 3 |
Correct |
44 ms |
3240 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1089 ms |
8804 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
11188 KB |
Output is correct |
| 2 |
Execution timed out |
1096 ms |
8804 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
9512 KB |
Output is correct |
| 2 |
Execution timed out |
1082 ms |
9060 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
47 ms |
11060 KB |
Output is correct |
| 2 |
Execution timed out |
1096 ms |
9828 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
39 ms |
9464 KB |
Output is correct |
| 2 |
Execution timed out |
1097 ms |
9064 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
9572 KB |
Output is correct |
| 2 |
Execution timed out |
1094 ms |
9576 KB |
Time limit exceeded |
