Submission #601565

#	Time	Username	Problem	Language	Result	Execution time	Memory
601565		enerelt14	Mechanical Doll (IOI18_doll)	C++14	0 / 100	1 ms	212 KiB

doll

#include "doll.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int>a;
int c[100005], x[400005], y[400005];
bool is[400005];
int m, k, la, q;
int tree[400005];
void go(int id, int l, int r){
  if(l==r){
    if (q==(1<<la))tree[id]=-(k+q);
    else tree[id]=a[q+k-1];
    return;
  }
  else tree[id]=-(k+id);
  int mid=(l+r)/2;
  if (!is[id]){
    go(id*2, l, mid);
    x[id+k]=tree[id*2];
    is[id]=1;
  }
  else{
    go(id*2+1, mid+1, r);
    y[id+k]=tree[id*2+1];
    is[id]=0;
  }
}
void solve(){
    la=0;
    while((1<<(la+1))<=m+1)la++;
    for (int i=1;i<(1<<la);i++){
      c[a[i+k-1]]=-(k+1);
      q=i;
      go(1, 1, (1<<la));
    }
    q++;
    go(1, 1, (1<<la));
    m-=((1<<la)-1);
    k+=((1<<la)-1);
    if (m==0){
        x[k+1]=-(k+1);
        y[k+1]=0;
    }
}
void create_circuit(int M, vector<int>A){
    for (int i=1;i<=M;i++)c[i]=0;
    a=A;
    m=A.size();
    while(m!=0){
        solve();
    }
    vector<int>X, Y, C;
    C.pb(-1);
    for (int i=1;i<=M;i++){
      C.pb(c[i]);
      cout<<c[i]<<" ";
    }
    cout<<"\n";
    for (int i=1;i<=A.size()+1;i++){
      X.pb(x[i]);
      cout<<x[i]<<" ";
    }
    cout<<"\n";
    for (int i=1;i<=A.size()+1;i++){
      Y.pb(y[i]);
      cout<<y[i]<<" ";
    }
    cout<<"\n";
    answer(C, X, Y);
}

Compilation message (stderr)

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

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