oj.uz

답안 #339652

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
339652 2020-12-25T19:05:33 Z Hazem Slagalica (COCI19_slagalica2) C++14
40 / 70
 1000 ms 11188 KB 
/*
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);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 46 ms 9832 KB Output is correct
2 Correct 34 ms 9612 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 9496 KB Output is correct
2 Correct 40 ms 9060 KB Output is correct

Subtask #5
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 2312 KB Output is correct
2 Correct 37 ms 3176 KB Output is correct

Subtask #6
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #7
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 37 ms 3068 KB Output is correct
2 Correct 31 ms 2184 KB Output is correct

Subtask #8
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #9
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1089 ms 8804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 11188 KB Output is correct
2 Execution timed out 1096 ms 8804 KB Time limit exceeded

Subtask #11
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 9512 KB Output is correct
2 Execution timed out 1082 ms 9060 KB Time limit exceeded

Subtask #12
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 11060 KB Output is correct
2 Execution timed out 1096 ms 9828 KB Time limit exceeded

Subtask #13
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 9464 KB Output is correct
2 Execution timed out 1097 ms 9064 KB Time limit exceeded

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 9572 KB Output is correct
2 Execution timed out 1094 ms 9576 KB Time limit exceeded