Submission #996301

#	Time	Username	Problem	Language	Result	Execution time	Memory
996301		PCTprobability	Mechanical Doll (IOI18_doll)	C++17	100 / 100	88 ms	17260 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;
void create_circuit(int m, std::vector<int> a) {
  a.push_back(0);
  int n=a.size();
  vector<int> c(m+1);
  for(int i=0;i<=m;i++){
    c[i]=-1;
  }
  int nowi=2,s=1,bt=0;
  while(nowi<n){
    nowi*=2;
    s*=2;
    s++;
    bt++;
  }
  vector<int> x(s+1,-1),y(s+1,-1);
  int now=0;
  x[0]=0;
  y[0]=0;
  for(int i=1;i<=s;i++){
    if(i*2<=s){
      x[i]=-i*2;
      y[i]=-i*2-1;
    }
  }
  vector<pair<int,int>> pq;
  for(int i=0;i<(s+1)/2;i++){
    int id=0;
    for(int j=0;j<bt;j++){
      if((i>>j)&1) id^=(1<<(bt-1-j));
    }
    pq.push_back({id,i+(s+1)/2});
  }
  sort(pq.begin(),pq.end());
  vector<int> xs(s+1),ys(s+1);
  for(int i=0;i<pq.size();i++){
    xs[pq[i].second]=i;
    ys[pq[i].second]=i+(s+1)/2;
  }
  pq.clear();
  for(int i=s;i>=(s+1)/2;i--){
    if(pq.size()<a.size()){
      pq.push_back({xs[i],i});
    }
    if(pq.size()<a.size()){
      pq.push_back({ys[i],i});
    }
  }
  sort(pq.begin(),pq.end());
  //for(auto e:pq) cout<<e.first<<" "<<e.second<<endl;
  for(int i=0;i<pq.size();i++){
    //cout<<pq[i].second<<" "<<a[i]<<endl;
    if(x[pq[i].second]==-1){
      x[pq[i].second]=a[i];
    }
    else{
      y[pq[i].second]=a[i];
    }
  }
  /*for(auto e:x) cout<<e<<" ";
  cout<<endl;
  for(auto e:y) cout<<e<<" ";
  cout<<endl;*/
  vector<int> use(s+1);
  for(int i=s;i>=1;i--){
    if(x[i]>=0||y[i]>=0) continue;
    if((x[i]==-1||use[-x[i]]==-1)&&(y[i]==-1||use[-y[i]]==-1)){
      use[i]=-1;
    }
  }
  vector<int> nid(s+1,1);
  int z=1;
  for(int i=1;i<=s;i++){
    if(use[i]!=-1){
      nid[i]=z;
      z++;
    }
  }
  /*for(auto e:nid) cout<<e<<" ";
  cout<<endl;*/
  vector<int> X,Y;
  for(int i=1;i<=s;i++){
    if(use[i]!=-1){
      //cout<<i<<" "<<x[i]<<" "<<y[i]<<endl;
      if(x[i]>=0) X.push_back(x[i]);
      else X.push_back(-nid[-x[i]]);
      if(y[i]>=0) Y.push_back(y[i]);
      else Y.push_back(-nid[-y[i]]);
    }
  }
  /*for(auto e:x) cout<<e<<" ";
  cout<<endl;
  for(auto e:y) cout<<e<<" ";
  cout<<endl;
  for(auto e:X) cout<<e<<" ";
  cout<<endl;
  for(auto e:Y) cout<<e<<" ";
  cout<<endl;*/
  answer(c,X,Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:38:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int i=0;i<pq.size();i++){
      |               ~^~~~~~~~~~
doll.cpp:53:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |   for(int i=0;i<pq.size();i++){
      |               ~^~~~~~~~~~
doll.cpp:19:7: warning: unused variable 'now' [-Wunused-variable]
   19 |   int now=0;
      |       ^~~

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