Submission #415672

#	Time	Username	Problem	Language	Result	Execution time	Memory
415672		Ahmadsm2005	Mechanical Doll (IOI18_doll)	C++14	37 / 100	165 ms	11660 KiB

doll

    #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 (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:24:12: 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:18: 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:11: 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:18: 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:18: 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:9: warning: unused variable 'N' [-Wunused-variable]
   58 |     int N = A.size();
      |         ^

• Subtask 1: 0 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 9 / 18
• Subtask 6: 28 / 56