Submission #339652

#	Time	Username	Problem	Language	Result	Execution time	Memory
339652		Hazem	Slagalica (COCI19_slagalica2)	C++14	40 / 70	1097 ms	11188 KiB

slagalica

/*
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 (stderr)

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);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 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