oj.uz

Submission #258191

# Submission time Handle Problem Language Result Execution time Memory
258191 2020-08-05T14:02:06 Z sonvip9 Slagalica (COCI19_slagalica2) C++14
40 / 70
 165 ms 3808 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ii pair <int,int>
#define pl pair <ll,ll>
#define fr(i,x,y) for (int i=x;i<=y;i++)
#define ft(i,x,y) for (int i=y;i>=x;i--)
#define N 100005
using namespace std ;
int d[8][8],dd[12],ans[N],cnt[9];
struct data{
    int tpe;
    int w ;
};
int n,x[12];
data puz[N];
vector <int> ans_sub2[9];
void inp()
{
    ios_base::sync_with_stdio(false) ;
    cin.tie(0);
    cout.tie(0);
   //// freopen("Slagalica.inp","r",stdin) ;
   // freopen("Slagalica.out","w",stdout);
    cin>> n;
    fr(i,1,n) {
         cin>>puz[i].tpe>>puz[i].w;
    }
    d[1][3] = 1,d[1][4] = 1 ,d[1][8] = 1 ;
    d[2][1] = 1,d[2][7] = 1,d[2][2] = 1;
    d[3][4] = 1,d[3][8] = 1,d[3][3] = 1;
    d[4][1] = 1,d[4][2] = 1 ,d[4][7] = 1 ;
    d[5][3] = 1,d[5][4] = 1 ,d[5][8] = 1 ;
    d[6][1] = 1,d[6][2] = 1 ,d[6][7] = 1 ;
    ans[1] = INT_MAX ;
    fr(i,1,n) {
       cnt[puz[i].tpe]++;
       ans_sub2[puz[i].tpe].push_back(puz[i].w);
    }
    fr(i,1,8) sort(ans_sub2[i].begin(),ans_sub2[i].end());
}
void show(){
   if (puz[x[1]].tpe!=5 and puz[x[1]].tpe!=6) return ;
   data g[12];
   g[1] = puz[x[1]];
   int dem_show = 1 ;
   fr(i,1,n-1) {
      if (d[puz[x[i]].tpe][puz[x[i+1]].tpe]==1){
          g[++dem_show] = puz[x[i+1]];
      }
      if (puz[x[i+1]].tpe==7 or puz[x[i+1]].tpe==8) break;
   }
   if (dem_show!=n) return ;
   if (g[dem_show].tpe!= 7 and g[dem_show].tpe!=8) return ;
   fr(i,1,n){
     if (g[i].w<=ans[i]) {
         if (g[i].w==ans[i]) continue ;
         else {
            fr(j,1,n) ans[j] = g[j].w ;
            break ;
         }
     }
     else break ;
   }
}
void hoanvi(int u){
    if (u==n+1){
        show();
        return ;
    }
    fr(i,1,n){
       if (dd[i]==0){
           x[u] = i ;
           dd[i] = 1 ;
           hoanvi(u+1) ;
           dd[i] = 0;
       }
    }
}
void sub1()
{
    hoanvi(1);
    if (ans[1]==INT_MAX) cout<<"-1";
    else
    fr(i,1,n) cout<<ans[i]<<" ";
}
void sub2(){
    fr(i,1,8) dd[i] = INT_MAX;
    if (cnt[5]*cnt[6]!=0) {
        cout<<"-1" ;
        return ;
    }
    if (cnt[6]==1){
        if (ans_sub2[1].size()!=ans_sub2[4].size() or cnt[6]+cnt[7]!=2 or cnt[1]==0){
            cout<<"-1";
        }
        else {
            cout<<ans_sub2[6][0]<<" ";
            fr(i,0,ans_sub2[4].size()-1) cout<<ans_sub2[1][i]<<" "<<ans_sub2[4][i]<<" ";
            cout<<ans_sub2[7][0]<<" ";
        }
        return ;
    }
    if (cnt[5]==1){
        if (ans_sub2[1].size()!=ans_sub2[4].size() or cnt[5]+cnt[8]!=2 or cnt[1]==0){
            if (cnt[7]==1 and (int)ans_sub2[4].size()-(int)ans_sub2[1].size()==1){
                cout<<ans_sub2[5][0]<<" ";
                fr(i,0,ans_sub2[1].size()-1) cout<<ans_sub2[4][i]<<" "<<ans_sub2[1][i]<<" ";
                cout<<ans_sub2[4][ans_sub2[4].size()-1]<<" "<<ans_sub2[7][0];
                return ;
            }
            cout<<"-1";
        }
        else {
            cout<<ans_sub2[5][0]<<" ";
            fr(i,0,ans_sub2[4].size()-1) cout<<ans_sub2[4][i]<<" "<<ans_sub2[1][i]<<" ";
            cout<<ans_sub2[8][0]<<" ";
        }
        return ;
    }
    cout<<"-1";
}
void sub3(){
    if (cnt[5]*cnt[6]!=0 or cnt[7]*cnt[8]!=0){
        cout<<"-1";
        return ;
    }
    //cout<<cnt[5]<<" "<<cnt[6]<<" "<<cnt[1]<<" "<<cnt[4]<<" "<<cnt[2]<<" "<<cnt[3]<<" "<<cnt[8]<<endl;
    if (cnt[1]==0 and cnt[4]==0){
        if (cnt[6]==1){
            if (cnt[7]==1 and n-cnt[6]-cnt[7]==cnt[2]) {
                cout<<ans_sub2[6][0]<<" ";
                for (int v:ans_sub2[2]) cout<<v<<" ";
                cout<<ans_sub2[7][0]<<" ";
            }
            else cout<<"-1";
        }
        if (cnt[5]==1){
            if (cnt[8]==1 and n-cnt[5]-cnt[8]==cnt[3]) {
                cout<<ans_sub2[5][0]<<" ";
                for (int v:ans_sub2[3]) cout<<v<<" ";
                cout<<ans_sub2[8][0]<<" ";
            }
            else cout<<"-1";
        }
        return ;
    }
    if (cnt[1]==0 and cnt[4]!=0){
        if (cnt[6]==1){
            cout<<"-1";
        }
        if (cnt[5]==1){
            if (cnt[7]==1 and n-cnt[7]-cnt[5]-cnt[4]==cnt[2])
            {
                cout<<ans_sub2[5][0]<<" "<<ans_sub2[4][0]<<" ";
                for (int v:ans_sub2[2]) cout<<v<<" ";
                cout<<ans_sub2[7][0]<<" ";
            }
            else
               if (cnt[7]==1 and n-cnt[2]-cnt[5]-cnt[7]-cnt[4]==cnt[3]){
                   cout<<ans_sub2[5][0]<<" ";
                   for (int v:ans_sub2[3]) cout<<v<<" ";
                   cout<<ans_sub2[4][0]<<" ";
                   for (int v:ans_sub2[2]) cout<<v<<" ";
                   cout<<ans_sub2[7][0]<<" ";
               }
                 else
                    cout<<"-1";
        }
        return ;
    }
    if (cnt[4]==0 and cnt[1]!=0){
        if (cnt[5]==1){
            cout<<"-1";
        }
        if (cnt[6]==1){
            if (cnt[8]==1 and n-cnt[8]-cnt[6]-cnt[1]==cnt[3])
            {
                cout<<ans_sub2[6][0]<<" "<<ans_sub2[1][0]<<" ";
                for (int v:ans_sub2[3]) cout<<v<<" ";
                cout<<ans_sub2[8][0]<<" ";
            }
            else
               if (cnt[8]==1 and n-cnt[6]-cnt[2]-cnt[1]-cnt[8]==cnt[3]){
                   cout<<ans_sub2[6][0]<<" ";
                   for (int v:ans_sub2[2]) cout<<v<<" ";
                   cout<<ans_sub2[1][0]<<" ";
                   for (int v:ans_sub2[3]) cout<<v<<" ";
                   cout<<ans_sub2[8][0]<<" ";
               }
                 else
                    cout<<"-1";
        }
        return ;
    }
    if (cnt[4]==1 and cnt[1]==1){
       if (cnt[5]==1){
           if (n-cnt[5]-cnt[4]-cnt[1]-cnt[8]==cnt[3]){
                cout<<ans_sub2[5][0]<<" "<<ans_sub2[4][0]<<" "<<ans_sub2[1][0]<<" ";
                for (int v:ans_sub2[3]) cout<<v<<" ";
                cout<<ans_sub2[8][0]<<" ";
           }
           else cout<<"-1";
       }
       if (cnt[6]==1){
            if (n-cnt[6]-cnt[4]-cnt[1]-cnt[7]==cnt[2]){
                cout<<ans_sub2[6][0]<<" "<<ans_sub2[1][0]<<" "<<ans_sub2[4][0]<<" ";
                for (int v:ans_sub2[2]) cout<<v<<" ";
                cout<<ans_sub2[7][0]<<" ";
           }
           else cout<<"-1";
       }
    }
}
int main()
{
    inp();
    if (n<=10) sub1();
    else{
      if (cnt[2]==0 and cnt[3]==0)
      sub2();
      else
         sub3();
    }
}

Compilation message

slagalica.cpp: In function 'void sub2()':
slagalica.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fr(i,x,y) for (int i=x;i<=y;i++)
slagalica.cpp:101:16:
             fr(i,0,ans_sub2[4].size()-1) cout<<ans_sub2[1][i]<<" "<<ans_sub2[4][i]<<" ";
                ~~~~~~~~~~~~~~~~~~~~~~~~
slagalica.cpp:101:13: note: in expansion of macro 'fr'
             fr(i,0,ans_sub2[4].size()-1) cout<<ans_sub2[1][i]<<" "<<ans_sub2[4][i]<<" ";
             ^~
slagalica.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fr(i,x,y) for (int i=x;i<=y;i++)
slagalica.cpp:110:20:
                 fr(i,0,ans_sub2[1].size()-1) cout<<ans_sub2[4][i]<<" "<<ans_sub2[1][i]<<" ";
                    ~~~~~~~~~~~~~~~~~~~~~~~~
slagalica.cpp:110:17: note: in expansion of macro 'fr'
                 fr(i,0,ans_sub2[1].size()-1) cout<<ans_sub2[4][i]<<" "<<ans_sub2[1][i]<<" ";
                 ^~
slagalica.cpp:8:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define fr(i,x,y) for (int i=x;i<=y;i++)
slagalica.cpp:118:16:
             fr(i,0,ans_sub2[4].size()-1) cout<<ans_sub2[4][i]<<" "<<ans_sub2[1][i]<<" ";
                ~~~~~~~~~~~~~~~~~~~~~~~~
slagalica.cpp:118:13: note: in expansion of macro 'fr'
             fr(i,0,ans_sub2[4].size()-1) cout<<ans_sub2[4][i]<<" "<<ans_sub2[1][i]<<" ";
             ^~
slagalica.cpp: In function 'void inp()':
slagalica.cpp:31:36: warning: array subscript is above array bounds [-Warray-bounds]
     d[1][3] = 1,d[1][4] = 1 ,d[1][8] = 1 ;
                              ~~~~~~^
slagalica.cpp:33:23: warning: array subscript is above array bounds [-Warray-bounds]
     d[3][4] = 1,d[3][8] = 1,d[3][3] = 1;
                 ~~~~~~^
slagalica.cpp:35:36: warning: array subscript is above array bounds [-Warray-bounds]
     d[5][3] = 1,d[5][4] = 1 ,d[5][8] = 1 ;
                              ~~~~~~^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 404 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 384 KB Output is correct
2 Correct 153 ms 384 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3452 KB Output is correct
2 Correct 28 ms 2692 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3252 KB Output is correct
2 Correct 29 ms 2676 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 2940 KB Output is correct
2 Correct 37 ms 3408 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2680 KB Output is correct
2 Correct 35 ms 3232 KB Output is correct
3 Correct 39 ms 3808 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3444 KB Output is correct
2 Correct 28 ms 2676 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 3444 KB Output is correct
2 Correct 30 ms 2592 KB Output is correct
3 Correct 38 ms 3708 KB Output is correct

Subtask #9
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 2688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 2944 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 2412 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 29 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 2560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 2484 KB Output isn't correct
2 Halted 0 ms 0 KB -