Submission #292596

#	Time	Username	Problem	Language	Result	Execution time	Memory
292596		Fasho	Mechanical Doll (IOI18_doll)	C++14	0 / 100	3 ms	2636 KiB

doll

#include <algorithm>
#include <iostream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <cstdio>
#include <string>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;
#define NN 100005
#define ll long long int
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll> 
#define fast2 freopen ("in.txt","r",stdin);freopen ("out.txt","w",stdout);
#define mod 1000000007
#include "doll.h"
using namespace std;

ll t,n,m,sum,ar[NN],pw[NN],cnt,ans[NN],ans1[NN],ans2[NN];



vector<int> v[NN],anss,X,Y;

bool check(int ind,int depth,int x,int y)
{
  if(x+pw[depth]>=v[y].size())
    return 0;
  return 1;
}

void build(int ind,int depth,int x,int y)
{
  // cerr<<ind<<sp<<depth<<endl;
  cnt++;
  ll xx=cnt;

  if(check(ind*2,depth+1,x,y))
  {
    ans1[xx]=-(cnt+1);
    build(ind*2,depth+1,x,y);
  }
  else
    ans1[xx]=v[y][x];
  if(check(ind*2,depth+1,x+pw[depth],y))
  {
    ans2[xx]=-(cnt+1);
    build(ind*2+1,depth+1,x+pw[depth],y);
  }
  else
    ans2[xx]=v[y][x+pw[depth]];
}

void create_circuit(int M, std::vector<int> A) {
  n = A.size();
  m=M;
  std::vector<int> C(M + 1);
  fo(i,1,n)
    ar[i]=A[i-1];
  ar[0]=0;
  ar[n+1]=0;
  pw[0]=1;
  fo(i,1,62)
    pw[i]=pw[i-1]*2;
  fo(i,1,n)
    v[ar[i]].pb(ar[i+1]);
  // build(1,0,0,1);
  // cnt+=v[1].size()-1;
  // fo(i,1,cnt)
  //   cout<<ans1[i]<<sp<<ans2[i]<<endl;
  for(int i=0;i<=m;i++)
  {
    if(v[i].size()==1)
    {
      ans[i]=v[i][0];
      continue;
    }
    if(v[i].size()==0)
    {
      ans[i]=1;
      continue;
    }
    ans[i]=-(cnt+1);
    build(1,0,0,i);
  }
  for(int i=1;i<=cnt;i++)
    X.pb(ans1[i]),Y.pb(ans2[i]);
  fo(i,0,m)
    anss.pb(ans[i]);
  // fo(i,0,m)
  //   cout<<anss[i]<<sp;
  //   cout<<endl;
  // fo(i,0,cnt-1)
  //   cout<<X[i]<<sp<<Y[i]<<endl;

  answer(anss, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'bool check(int, int, int, int)':
doll.cpp:44:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if(x+pw[depth]>=v[y].size())
      |      ~~~~~~~~~~~^~~~~~~~~~~~~

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