oj.uz

Submission #413312

# Submission time Handle Problem Language Result Execution time Memory
413312 2021-05-28T13:25:28 Z Ahmadsm2005 Mechanical Doll (IOI18_doll) C++14
46 / 100
 194 ms 11656 KB 
#include "doll.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
int freq[200002],seg[800002],state[800002],depth,TOTSTATE,X[800002],Y[800002];
void upd(int v,int idx=0,int DEPTH=0){
if(DEPTH==depth){
if(!state[idx])
X[idx]=v,TOTSTATE++,state[idx]=1;
else
state[idx]=0,TOTSTATE--,Y[idx]=v;
return;
}
if(!state[idx]){
state[idx]=1,TOTSTATE++,upd(v,idx*2+1,DEPTH+1);
}
else{
state[idx]=0,TOTSTATE--,upd(v,idx*2+2,DEPTH+1);
}
X[idx]=-(idx*2+2),Y[idx]=-(idx*2+3);
}
void create_circuit(int M,vector<int>A){
int Q=1;
while(Q<=A.size())
Q*=2,depth++;
if(M==1){
int N = A.size();
vector<int> C(M + 1);
C[0] = -1;
for (int i = 1; i <= M; ++i) {
C[i] = -1;
}
vector<int>X,Y;
string s;
while(N){
s+=('0'+N%2);
N/=2;
}
reverse(s.begin(),s.end());
for(int i=0;i<s.size();i++){
if(s[i]=='1')
X.push_back(1);
else
X.push_back(-1);
if(i+1!=s.size())
Y.push_back((-i)-2);
}
Y.push_back(0);
/*for(int i=0;i<X.size();i++)
cout<<X[i]<<' ';
cout<<endl;
for(int i=0;i<Y.size();i++)
cout<<Y[i]<<' ';*/
answer(C, X, Y);
return;
}
freq[0]++;
int N = A.size();
for(int i=0;i<A.size();i++)
freq[A[i]]++;
vector<int> C(M + 1);
for(int i=0;i<=M;i++)
C[i]=-1;
int TOT=Q;
//cout<<TOT<<' '<<depth<<endl;
//exit(0);
TOT--;
depth--;
for(int i=0;i<A.size();i++){
upd(A[i]);
TOT--;
}
while(TOT){
upd(-1);
TOT--;
}
upd(0);
vector<int>XX,YY;
//cout<<TOTSTATE<<endl;
//for(int i=0;i<Q-1;i++)
//cout<<X[i]<<' '<<Y[i]<<endl;
for(int i=0;i<Q-1;i++)
XX.push_back(X[i]),YY.push_back(Y[i]);
answer(C,XX,YY);
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:24:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | while(Q<=A.size())
      |       ~^~~~~~~~~~
doll.cpp:40:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 | for(int i=0;i<s.size();i++){
      |             ~^~~~~~~~~
doll.cpp:45:7: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 | if(i+1!=s.size())
      |    ~~~^~~~~~~~~~
doll.cpp:59:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 | for(int i=0;i<A.size();i++)
      |             ~^~~~~~~~~
doll.cpp:69:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 | for(int i=0;i<A.size();i++){
      |             ~^~~~~~~~~
doll.cpp:58:5: warning: unused variable 'N' [-Wunused-variable]
   58 | int N = A.size();
      |     ^

Subtask #1
0 / 2.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 10.0

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

Subtask #4
0 / 10.0

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

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 17 ms 1340 KB Output is correct
3 Correct 17 ms 1228 KB Output is correct
4 Correct 35 ms 1868 KB Output is correct

Subtask #6
28.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 17 ms 1340 KB Output is correct
3 Correct 17 ms 1228 KB Output is correct
4 Correct 35 ms 1868 KB Output is correct
5 Partially correct 153 ms 11656 KB Output is partially correct
6 Partially correct 194 ms 11440 KB Output is partially correct
7 Partially correct 157 ms 11568 KB Output is partially correct
8 Partially correct 159 ms 11440 KB Output is partially correct
9 Partially correct 140 ms 10800 KB Output is partially correct
10 Partially correct 160 ms 11324 KB Output is partially correct
11 Partially correct 148 ms 11228 KB Output is partially correct
12 Partially correct 149 ms 10704 KB Output is partially correct
13 Partially correct 138 ms 10916 KB Output is partially correct
14 Partially correct 172 ms 10956 KB Output is partially correct
15 Partially correct 172 ms 10928 KB Output is partially correct
16 Partially correct 6 ms 704 KB Output is partially correct
17 Correct 72 ms 6120 KB Output is correct
18 Partially correct 133 ms 10808 KB Output is partially correct
19 Partially correct 125 ms 10724 KB Output is partially correct
20 Partially correct 141 ms 11292 KB Output is partially correct
21 Partially correct 161 ms 11344 KB Output is partially correct
22 Partially correct 163 ms 11232 KB Output is partially correct