Submission #1231274

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231274		acoatoitgs	Mechanical Doll (IOI18_doll)	C++20	Compilation error	0 ms	0 KiB

doll

#include "doll.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;

#define ll int
#define all(a) (a).begin(), (a).end()

void create_circuit(int M, vector<int> A) {
  int N = A.size();
  A.push_back(0);

  vector<int> C(M + 1);
  vector<vector<pair<int,int>>> con(M+1);

  bitset<100005> uniq;
  uniq.flip();
  bitset<100005> seen;


  for(ll i = 0; i < N; i++)
  {
    if(seen[A[i]]) uniq[A[i]] = 0;
    seen[A[i]] = 1;
  }
  int len = 0;
  int nx = -1;

  for(int i = 0; i < N; i++) 
  {
    len += (!uniq[A[i]]);
  }
  for(int i = 1; i <= M; i++)
  {
    if(!seen[i]) C[i] = 0;
  }

  // cout << "LEN: " <<  len << "\n";
  vector<int> X(N + 50), Y(N + 50);

  C[0] = A[0];  

  int depth = max(1, (__builtin_popcount(len) == 1) ? 
    __bit_width((uint32_t)len)-1 : 
    __bit_width((uint32_t)len));
  
  int first_node = -1;
  // cout << depth << " " << first_node << "\n";
  vector<pair<ll,pair<ll, bool>>> tm;
  function<int(int, int)> prop = [&](int val, int dep) -> int
  {
    // cout << val << " " << dep << "\n";
    int node = nx;
    nx--;
    if(dep == depth-1)
    {
      int val1 = val;
      int val2 = val + (1<<dep);
      
      if(tm.size() < len)
      {
        tm.push_back({val1, {node, 0}});
        tm.push_back({val2, {node, 1}});
        return node;
      }
      else
      {
        nx++;
        return first_node;
      }
    }
    else
    {
      int y = prop(val+(1<<dep), dep+1);
      int x = prop(val, dep+1);

      X[-(node+1)] = x;
      Y[-(node+1)] = y;
      return node;
    }
  };
  if(len != 0)
    prop(0, 0);

  // cout << "SZ: " << tm.size() << "\n";
  sort(all(tm), greater<pair<ll, pair<ll, bool>>>());
  int idx = 0;
  while(len > 1 && idx < N)
  {
    if(uniq[A[idx]])
    {
      C[A[idx]] = A[idx+1];
      idx++;
      continue;
    }
    else C[A[idx]] = first_node;
    int to = A[idx+1];

    auto [node, r] = tm.back().second;
    tm.pop_back();
    
    if(r) Y[-(node+1)] = to;
    else X[-(node+1)] = to;
    idx++;
    len--;
  }
  // cout << len << " " << idx << "\n";
  while(tm.size() != 1)
  {
    auto [node, r] = tm.back().second;
    tm.pop_back();
    
    if(r) Y[-(node+1)] = -1;
    else X[-(node+1)] = -1;
  }

  while(idx < N)
  {
    // cout << "In: " << idx << " " << uniq[A[idx]] << " " << tm.size() << "\n";
    if(uniq[A[idx]])
    {
      C[A[idx]] = A[idx+1];
      idx++;
      continue;
    }
    else C[A[idx]] = first_node;
    int to = A[idx+1];

    auto [node, r] = tm.back().second;
    tm.pop_back();
    
    if(r) Y[-(node+1)] = to;
    else X[-(node+1)] = to;
    idx++;
    len--;
  }

  X.resize(-(nx+1));
  Y.resize(-(nx+1));

  answer(C, X, Y);
}

Compilation message (stderr)

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:43:18: error: no matching function for call to 'max(int, unsigned int)'
   43 |   int depth = max(1, (__builtin_popcount(len) == 1) ?
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   44 |     __bit_width((uint32_t)len)-1 :
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   45 |     __bit_width((uint32_t)len));
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from doll.h:3,
                 from doll.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
doll.cpp:43:18: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'unsigned int')
   43 |   int depth = max(1, (__builtin_popcount(len) == 1) ?
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   44 |     __bit_width((uint32_t)len)-1 :
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   45 |     __bit_width((uint32_t)len));
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from doll.h:3,
                 from doll.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
doll.cpp:43:18: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'unsigned int')
   43 |   int depth = max(1, (__builtin_popcount(len) == 1) ?
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   44 |     __bit_width((uint32_t)len)-1 :
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   45 |     __bit_width((uint32_t)len));
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from doll.h:3,
                 from doll.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3461:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3461 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3461:5: note:   template argument deduction/substitution failed:
doll.cpp:43:18: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   43 |   int depth = max(1, (__builtin_popcount(len) == 1) ?
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   44 |     __bit_width((uint32_t)len)-1 :
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   45 |     __bit_width((uint32_t)len));
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from doll.h:3,
                 from doll.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3467:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3467 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3467:5: note:   template argument deduction/substitution failed:
doll.cpp:43:18: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   43 |   int depth = max(1, (__builtin_popcount(len) == 1) ?
      |               ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   44 |     __bit_width((uint32_t)len)-1 :
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   45 |     __bit_width((uint32_t)len));
      |     ~~~~~~~~~~~~~~~~~~~~~~~~~~~