oj.uz

Submission #75125

# Submission time Handle Problem Language Result Execution time Memory
75125 2018-09-08T12:31:33 Z faustaadp Mechanical Doll (IOI18_doll) C++17
53 / 100
 180 ms 22700 KB 
#include "doll.h"
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
ll i,Sa=0,DU[202020],j,TR;
vector<ll> v[202020],isi;
vector<int> C,XXI,YYI;
void gawe(ll aa,ll bb,ll cc,ll dd)
{
    //cout<<i<<" "<<aa<<" "<<bb<<" "<<cc<<"\n";
    if(aa==1)
    {
       // cout<<bb<<"\n";
        XXI[dd]=(isi[bb]);
        YYI[dd]=(isi[bb+(1<<(cc-1))]);
        return ;
    }
    TR++;
    XXI[dd]=-TR-1;
    gawe(aa-1,bb,cc,TR);
    TR++;
    YYI[dd]=-TR-1;
  //  cout<<i<<" "<<cc<<" "<<aa<<" "<<(1<<(cc-aa))<<"\n";
    gawe(aa-1,bb+(1<<(cc-aa)),cc,TR);
}
void create_circuit(int M, std::vector<int> A) {
    int N = A.size();
    for(i=0;i<=M;i++)
        C.pb(0);
    v[0].pb(A[0]);
    for(i=0;i<N-1;i++)
        v[A[i]].pb(A[i+1]);
    for(i=0;i<=200000;i++)
    {
        for(j=20;j>=0;j--)
        {
            ll HA=(1<<j);
            if(HA>=i)
                DU[i]=j;
        }
    }
    v[A[N-1]].pb(0);
    //return ;
    for(i=0;i<=M;i++)
    {
        if(v[i].size()==0)
            continue;
        else
        if(v[i].size()==1)
        {
          //  cout<<v[i][0]<<"\n";
            C[i]=v[i][0];
            continue;
        }
        else
        {
            C[i]=-TR-1;
            ll SZ=v[i].size();
            ll GED=DU[SZ];
            //cout<<SZ<<" "<<GED<<"\n";
            isi.clear();
           // cout<<GED<<"GED\n";
            for(j=0;j<((1<<GED)-SZ);j++)
                isi.pb(-TR-1);
            for(j=0;j<v[i].size();j++)
                isi.pb(v[i][j]);
            for(j=1;j<isi.size();j++)
            {
                XXI.pb(0);
                YYI.pb(0);
       //         cout<<j<<" "<<isi[j]<<"\n";
            }
            gawe(GED,0,GED,TR);
            TR=XXI.size();
         //   TR+=isi.size();
            //TR+=GED;
        }
    }
//    for(i=0;i<=M;i++)cout<<i<<" "<<C[i]<<"\n";
  //  for(i=0;i<XXI.size();i++)cout<<-i-1<<" "<<XXI[i]<<" "<<YYI[i]<<"\n";
  //  cout<<C.size()<<" "<<XXI.size()<<" "<<YYI.size()<<"\n";
    answer(C, XXI, YYI);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:69:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for(j=0;j<v[i].size();j++)
      |                     ~^~~~~~~~~~~~
doll.cpp:71:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |             for(j=1;j<isi.size();j++)
      |                     ~^~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6604 KB Output is correct
2 Correct 57 ms 10296 KB Output is correct
3 Correct 41 ms 9956 KB Output is correct
4 Correct 14 ms 6556 KB Output is correct
5 Correct 22 ms 7848 KB Output is correct
6 Correct 53 ms 11588 KB Output is correct
7 Correct 12 ms 6484 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6604 KB Output is correct
2 Correct 57 ms 10296 KB Output is correct
3 Correct 41 ms 9956 KB Output is correct
4 Correct 14 ms 6556 KB Output is correct
5 Correct 22 ms 7848 KB Output is correct
6 Correct 53 ms 11588 KB Output is correct
7 Correct 12 ms 6484 KB Output is correct
8 Correct 97 ms 12728 KB Output is correct
9 Correct 76 ms 12660 KB Output is correct
10 Correct 138 ms 15220 KB Output is correct
11 Correct 14 ms 6604 KB Output is correct
12 Correct 15 ms 6504 KB Output is correct
13 Correct 17 ms 6552 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6604 KB Output is correct
2 Correct 57 ms 10296 KB Output is correct
3 Correct 41 ms 9956 KB Output is correct
4 Correct 14 ms 6556 KB Output is correct
5 Correct 22 ms 7848 KB Output is correct
6 Correct 53 ms 11588 KB Output is correct
7 Correct 12 ms 6484 KB Output is correct
8 Correct 97 ms 12728 KB Output is correct
9 Correct 76 ms 12660 KB Output is correct
10 Correct 138 ms 15220 KB Output is correct
11 Correct 14 ms 6604 KB Output is correct
12 Correct 15 ms 6504 KB Output is correct
13 Correct 17 ms 6552 KB Output is correct
14 Correct 154 ms 18860 KB Output is correct
15 Correct 81 ms 12232 KB Output is correct
16 Correct 120 ms 15276 KB Output is correct
17 Correct 15 ms 6604 KB Output is correct
18 Correct 16 ms 6592 KB Output is correct
19 Correct 16 ms 6540 KB Output is correct
20 Correct 146 ms 17276 KB Output is correct
21 Correct 17 ms 6664 KB Output is correct
22 Correct 14 ms 6604 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
9.0000000036 / 18.0

# Verdict Execution time Memory Grader output
1 Partially correct 16 ms 6532 KB Output is partially correct
2 Correct 62 ms 13760 KB Output is correct
3 Partially correct 106 ms 19336 KB Output is partially correct
4 Partially correct 111 ms 20060 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 16 ms 6532 KB Output is partially correct
2 Correct 62 ms 13760 KB Output is correct
3 Partially correct 106 ms 19336 KB Output is partially correct
4 Partially correct 111 ms 20060 KB Output is partially correct
5 Partially correct 180 ms 20100 KB Output is partially correct
6 Partially correct 131 ms 21240 KB Output is partially correct
7 Partially correct 154 ms 20904 KB Output is partially correct
8 Partially correct 152 ms 21964 KB Output is partially correct
9 Partially correct 106 ms 16364 KB Output is partially correct
10 Partially correct 167 ms 22452 KB Output is partially correct
11 Partially correct 140 ms 22700 KB Output is partially correct
12 Partially correct 110 ms 17184 KB Output is partially correct
13 Partially correct 111 ms 16196 KB Output is partially correct
14 Partially correct 120 ms 15796 KB Output is partially correct
15 Partially correct 114 ms 15284 KB Output is partially correct
16 Partially correct 19 ms 6860 KB Output is partially correct
17 Partially correct 99 ms 14728 KB Output is partially correct
18 Partially correct 102 ms 14776 KB Output is partially correct
19 Partially correct 91 ms 15380 KB Output is partially correct
20 Partially correct 137 ms 17960 KB Output is partially correct
21 Partially correct 123 ms 20392 KB Output is partially correct
22 Partially correct 132 ms 16920 KB Output is partially correct