oj.uz

Submission #264901

# Submission time Handle Problem Language Result Execution time Memory
264901 2020-08-14T10:59:18 Z sonvip9 Slagalica (COCI19_slagalica2) C++14
70 / 70
 49 ms 3960 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],sd[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+sd[i]]<minn and sd[i]<=ans_sub2[i].size()-1){
                minn = ans_sub2[i][0+sd[i]];
                leff = i;
            }
        }
     }
     if (minn==INT_MAX) return ;
     seq[++m].fi= minn;
     seq[m].se = leff ;
     sd[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 ;
     }
     //cout<<sd[mid]<<" "<<mid<<" "<<ans_sub2[mid].size()-1<<endl;
     fr(i,1,m){
        cout<<seq[i].fi<<" ";
        if (i==vt and ans_sub2[mid].size()!=0){
            for (int i=sd[mid];i<=(int)ans_sub2[mid].size()-1;i++)
                 cout<<ans_sub2[mid][i]<<" ";
        }
     }
}
int main()
{
    inp();
    sub4();
}

Compilation message

slagalica.cpp: In function 'void duyet(int)':
slagalica.cpp:44:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             if (ans_sub2[i][0+sd[i]]<minn and sd[i]<=ans_sub2[i].size()-1){
      |                                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

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

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3444 KB Output is correct
2 Correct 31 ms 2696 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3384 KB Output is correct
2 Correct 24 ms 2628 KB Output is correct

Subtask #5
5.0 / 5.0

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

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2192 KB Output is correct
2 Correct 32 ms 3188 KB Output is correct
3 Correct 49 ms 3552 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3316 KB Output is correct
2 Correct 25 ms 2292 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3316 KB Output is correct
2 Correct 24 ms 2300 KB Output is correct
3 Correct 35 ms 3572 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 2556 KB Output is correct
2 Correct 37 ms 3340 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3960 KB Output is correct
2 Correct 23 ms 2552 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3308 KB Output is correct
2 Correct 26 ms 2548 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 3852 KB Output is correct
2 Correct 26 ms 2808 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 3320 KB Output is correct
2 Correct 25 ms 2560 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3336 KB Output is correct
2 Correct 25 ms 2684 KB Output is correct