Submission #264880

# Submission time Handle Problem Language Result Execution time Memory
264880 2020-08-14T10:48:53 Z sonvip9 Slagalica (COCI19_slagalica2) C++14
10 / 70
1000 ms 2424 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[9][9],ans[N],cnt[9];
int n,m;
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);
    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 ;
    cin>> n;
    fr(i,1,n) {
         int u,v;
         cin>>u>>v ;
         cnt[u]++;
         ans_sub2[u].push_back(v);

    }
    fr(i,1,8) sort(ans_sub2[i].begin(),ans_sub2[i].end());
}
ii seq[N];
void duyet(int st){
     int minn=INT_MAX,leff;
     cnt[st]--;
     fr(i,1,8){
        if (d[st][i]==1 and ans_sub2[i].size()!=0 and i!=7 and i!=8){
            if (ans_sub2[i][0]<minn){
                minn = ans_sub2[i][0];
                leff = i;
            }
        }
     }
     if (minn==INT_MAX) return ;
     ans_sub2[leff].erase(ans_sub2[leff].begin()+0);
     seq[++m].fi= minn;
     seq[m].se = leff ;
     duyet(leff);
}
void sub4(){
     int st ;
     if (cnt[5]==1 and cnt[6] == 0) {
         st = 5;
     }
     else
        if (cnt[5]==0 and cnt[6]==1)  st = 6;
           else {
                cout<<"-1";
                return ;
           }
     int ed;
     if (cnt[7]==1 and cnt[8] == 0) {
         ed = 7;
     }
     else
        if (cnt[7]==0 and cnt[8]==1)  ed = 8;
           else {
                cout<<"-1";
                return ;
           }
     seq[++m].fi = ans_sub2[st][0];
     seq[m].se = st;
     duyet(st);
     seq[++m].fi = ans_sub2[ed][0];
     seq[m].se = ed;
     cnt[ed]--;
     if (d[seq[m-1].se][seq[m].se]!=1) {
          cout<<"-1";
          return ;
     }
     if (cnt[3]*cnt[2]!=0) {
         cout<<"-1";
         return ;
     }
     int mid = 3;
     if (cnt[3]==0) mid = 2 ;
     fr(i,1,8) {
         if (i!=mid and cnt[i]>0) {
              cout<<"-1" ;
              return ;
         }
     }
     int vt = INT_MAX ;
     fr(i,1,m-1){
        if (d[seq[i].se][mid] and d[mid][seq[i+1].se]) vt = i ;
     }
     fr(i,1,m){
        cout<<seq[i].fi<<" ";
        if (i==vt and ans_sub2[mid].size()!=0){
            for (int i=ans_sub2[mid].size()-cnt[mid];i<=(int)ans_sub2[mid].size()-1;i++)
                 cout<<ans_sub2[mid][i]<<" ";
        }
     }
}
int main()
{
    inp();
    sub4();
}

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 2244 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1088 ms 2100 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 2420 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 2060 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 2036 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 1920 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 2348 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 2424 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1074 ms 2148 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 2296 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 2132 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 1092 ms 2168 KB Time limit exceeded
2 Halted 0 ms 0 KB -