oj.uz

Submission #75128

# Submission time Handle Problem Language Result Execution time Memory
75128 2018-09-08T12:40:36 Z faustaadp Mechanical Doll (IOI18_doll) C++17
53 / 100
 179 ms 22768 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();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();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 11 ms 6604 KB Output is correct
2 Correct 55 ms 10264 KB Output is correct
3 Correct 44 ms 10040 KB Output is correct
4 Correct 9 ms 6604 KB Output is correct
5 Correct 24 ms 7820 KB Output is correct
6 Correct 89 ms 11580 KB Output is correct
7 Correct 9 ms 6600 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6604 KB Output is correct
2 Correct 55 ms 10264 KB Output is correct
3 Correct 44 ms 10040 KB Output is correct
4 Correct 9 ms 6604 KB Output is correct
5 Correct 24 ms 7820 KB Output is correct
6 Correct 89 ms 11580 KB Output is correct
7 Correct 9 ms 6600 KB Output is correct
8 Correct 132 ms 12760 KB Output is correct
9 Correct 110 ms 12712 KB Output is correct
10 Correct 121 ms 15176 KB Output is correct
11 Correct 11 ms 6528 KB Output is correct
12 Correct 12 ms 6580 KB Output is correct
13 Correct 10 ms 6656 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6604 KB Output is correct
2 Correct 55 ms 10264 KB Output is correct
3 Correct 44 ms 10040 KB Output is correct
4 Correct 9 ms 6604 KB Output is correct
5 Correct 24 ms 7820 KB Output is correct
6 Correct 89 ms 11580 KB Output is correct
7 Correct 9 ms 6600 KB Output is correct
8 Correct 132 ms 12760 KB Output is correct
9 Correct 110 ms 12712 KB Output is correct
10 Correct 121 ms 15176 KB Output is correct
11 Correct 11 ms 6528 KB Output is correct
12 Correct 12 ms 6580 KB Output is correct
13 Correct 10 ms 6656 KB Output is correct
14 Correct 147 ms 18780 KB Output is correct
15 Correct 78 ms 12224 KB Output is correct
16 Correct 127 ms 15188 KB Output is correct
17 Correct 15 ms 6604 KB Output is correct
18 Correct 13 ms 6484 KB Output is correct
19 Correct 10 ms 6604 KB Output is correct
20 Correct 123 ms 17244 KB Output is correct
21 Correct 12 ms 6488 KB Output is correct
22 Correct 9 ms 6604 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 6612 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 12 ms 6660 KB Output is partially correct
2 Correct 60 ms 13776 KB Output is correct
3 Partially correct 90 ms 19352 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 12 ms 6660 KB Output is partially correct
2 Correct 60 ms 13776 KB Output is correct
3 Partially correct 90 ms 19352 KB Output is partially correct
4 Partially correct 111 ms 20060 KB Output is partially correct
5 Partially correct 172 ms 20080 KB Output is partially correct
6 Partially correct 176 ms 21252 KB Output is partially correct
7 Partially correct 142 ms 20812 KB Output is partially correct
8 Partially correct 179 ms 22052 KB Output is partially correct
9 Partially correct 104 ms 16408 KB Output is partially correct
10 Partially correct 154 ms 22480 KB Output is partially correct
11 Partially correct 162 ms 22768 KB Output is partially correct
12 Partially correct 100 ms 17136 KB Output is partially correct
13 Partially correct 119 ms 16228 KB Output is partially correct
14 Partially correct 118 ms 15820 KB Output is partially correct
15 Partially correct 104 ms 15336 KB Output is partially correct
16 Partially correct 11 ms 6904 KB Output is partially correct
17 Partially correct 81 ms 14728 KB Output is partially correct
18 Partially correct 101 ms 14792 KB Output is partially correct
19 Partially correct 94 ms 15408 KB Output is partially correct
20 Partially correct 121 ms 17856 KB Output is partially correct
21 Partially correct 138 ms 20392 KB Output is partially correct
22 Partially correct 149 ms 16900 KB Output is partially correct