oj.uz

Submission #75129

# Submission time Handle Problem Language Result Execution time Memory
75129 2018-09-08T12:42:19 Z faustaadp Mechanical Doll (IOI18_doll) C++17
53 / 100
 221 ms 22764 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=0;j<isi.size()+9;j++)
            {
                XXI.pb(0);
                YYI.pb(0);
       //         cout<<j<<" "<<isi[j]<<"\n";
            }
            gawe(GED,0,GED,TR);
            TR=XXI.size();
            while((TR-1>=0)&&(XXI[TR-1]==0)&&(YYI[TR-1]==0))
            {
                XXI.pop_back();
                YYI.pop_back();
                TR--;
            }
         //   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";
  if(XXI.size()>N*2)
    while(1);
    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=0;j<isi.size()+9;j++)
      |                     ~^~~~~~~~~~~~~
doll.cpp:92:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |   if(XXI.size()>N*2)
      |      ~~~~~~~~~~^~~~
doll.cpp:92:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   92 |   if(XXI.size()>N*2)
      |   ^~
doll.cpp:94:5: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   94 |     answer(C, XXI, YYI);
      |     ^~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6504 KB Output is correct
2 Correct 51 ms 10332 KB Output is correct
3 Correct 39 ms 10016 KB Output is correct
4 Correct 10 ms 6604 KB Output is correct
5 Correct 22 ms 7876 KB Output is correct
6 Correct 61 ms 11740 KB Output is correct
7 Correct 10 ms 6604 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6504 KB Output is correct
2 Correct 51 ms 10332 KB Output is correct
3 Correct 39 ms 10016 KB Output is correct
4 Correct 10 ms 6604 KB Output is correct
5 Correct 22 ms 7876 KB Output is correct
6 Correct 61 ms 11740 KB Output is correct
7 Correct 10 ms 6604 KB Output is correct
8 Correct 106 ms 12916 KB Output is correct
9 Correct 84 ms 12736 KB Output is correct
10 Correct 149 ms 15256 KB Output is correct
11 Correct 10 ms 6536 KB Output is correct
12 Correct 10 ms 6604 KB Output is correct
13 Correct 9 ms 6504 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 6504 KB Output is correct
2 Correct 51 ms 10332 KB Output is correct
3 Correct 39 ms 10016 KB Output is correct
4 Correct 10 ms 6604 KB Output is correct
5 Correct 22 ms 7876 KB Output is correct
6 Correct 61 ms 11740 KB Output is correct
7 Correct 10 ms 6604 KB Output is correct
8 Correct 106 ms 12916 KB Output is correct
9 Correct 84 ms 12736 KB Output is correct
10 Correct 149 ms 15256 KB Output is correct
11 Correct 10 ms 6536 KB Output is correct
12 Correct 10 ms 6604 KB Output is correct
13 Correct 9 ms 6504 KB Output is correct
14 Correct 150 ms 18788 KB Output is correct
15 Correct 94 ms 12244 KB Output is correct
16 Correct 133 ms 15164 KB Output is correct
17 Correct 12 ms 6604 KB Output is correct
18 Correct 10 ms 6528 KB Output is correct
19 Correct 11 ms 6588 KB Output is correct
20 Correct 139 ms 17364 KB Output is correct
21 Correct 10 ms 6536 KB Output is correct
22 Correct 9 ms 6544 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 6584 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 10 ms 6624 KB Output is partially correct
2 Correct 61 ms 13452 KB Output is correct
3 Partially correct 108 ms 20012 KB Output is partially correct
4 Partially correct 107 ms 20768 KB Output is partially correct

Subtask #6
28.0000000112 / 56.0

# Verdict Execution time Memory Grader output
1 Partially correct 10 ms 6624 KB Output is partially correct
2 Correct 61 ms 13452 KB Output is correct
3 Partially correct 108 ms 20012 KB Output is partially correct
4 Partially correct 107 ms 20768 KB Output is partially correct
5 Partially correct 196 ms 20048 KB Output is partially correct
6 Partially correct 158 ms 21360 KB Output is partially correct
7 Partially correct 207 ms 20848 KB Output is partially correct
8 Partially correct 188 ms 22068 KB Output is partially correct
9 Partially correct 110 ms 18340 KB Output is partially correct
10 Partially correct 200 ms 22448 KB Output is partially correct
11 Partially correct 221 ms 22764 KB Output is partially correct
12 Partially correct 113 ms 17472 KB Output is partially correct
13 Partially correct 125 ms 16852 KB Output is partially correct
14 Partially correct 119 ms 16472 KB Output is partially correct
15 Partially correct 104 ms 16000 KB Output is partially correct
16 Partially correct 13 ms 6892 KB Output is partially correct
17 Partially correct 93 ms 15472 KB Output is partially correct
18 Partially correct 83 ms 15460 KB Output is partially correct
19 Partially correct 96 ms 16112 KB Output is partially correct
20 Partially correct 115 ms 18608 KB Output is partially correct
21 Partially correct 146 ms 21108 KB Output is partially correct
22 Partially correct 126 ms 17728 KB Output is partially correct