Submission #767025

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
767025	2023-06-26T10:23:04 Z	DJeniUp	Mechanical Doll (IOI18_doll)	C++17	Compilation error	0 ms	0 KB

doll

#include "doll.h"
#include <bits/stdc++.h>
using namespace std;

typedef int ll;
typedef pair<ll,ll>pairll;

#define pb push_back
#define fr first
#define sc second

ll h,a[400007],b[400007],f[400007],u[400007];

vector<ll>v[200007];

priority_queue<pairll,vector<pairll>, greater<pairll> >p;

vector<ll>c,x,y;

void create_circuit(int M, std::vector<int> A) {
    A.pb(0);
    for(int i=0;i<A.size()-1;i++){
        v[A[i]].pb(A[i+1]);
    }
    c.pb(A[0]);
    for(int i=1;i<=M;i++){
        if(v[i].size()==0)c.pb(0);
        else if(v[i].size()==1)c.pb(v[i][0]);
        else{
            h++;
            x.pb(-h);
            y.pb(-h);
            c.pb(-h);
            for(int j=0;j<v[i].size();j++){
                ll k=-c[i]-1;
                while(1){
                    if(f[k]%2==0){
                        f[k]++;
                        if(x[k]==-k-1){
                            x[k]=v[i][j];
                            break;
                        }else if(x[k]<0){
                            k=-x[k]-1;
                        }else{
                            h++;
                            f[h-1]=1;
                            x.pb(-h);
                            y.pb(-h);
                            x[h-1]=x[k];
                            x[k]=-h;
                            k=h-1;
                        }
                    }else{
                        f[k]++;
                        if(y[k]==-k-1){
                            y[k]=v[i][j];
                            break;
                        }else if(y[k]<0){
                            k=-y[k]-1;
                        }else{
                            h++;
                            f[h-1]=1;
                            x.pb(-h);
                            y.pb(-h);
                            x[h-1]=y[k];
                            y[k]=-h;
                            k=h-1;
                        }
                    }
                }
            }
        }
    }
    while(1){
        ll k=c[0];
        ll z=0;
        ll r=0;
        for(int i=0;i<h;i++){
            f[i]=0;
            u[i]=0;
        }
        while(p.size()>0)p.pop();
        ll pr=0;
        while(k!=0){
                r++;
            pr=k;
            if(k>0){
                k=c[k];
            }else{
                if(u[-k-1]==0)u[-i-1]=r;
                if(f[-k-1]%2==0){
                    p.push({u[-i-1],k});
                    f[-k-1]++;
                    k=x[-k-1];
                }else{

                    f[-k-1]++;
                    k=y[-k-1];
                }
            }
        }
        //cout<<p.back()<<" "<<f[-p.back()-1]<<endl;
        reverse(p.begin(),p.end());
        while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
        if(p.size()==0)break;
        while(p.size()>0){
            while(p.size()>0 && f[-p.back()-1]%2==0)p.pop();
            if(p.size()==0)break;
            z=p.top().sc;
            p.pop_back();
            //cout<<z<<endl;
            if(f[-z-1]%2==0){
                break;
            }else{
                if(pr>0)c[pr]=z;
                else{
                    if(f[-pr-1]%2==1)x[-pr-1]=z;
                    else y[-pr-1]=z;
                }
                k=-z-1;
                while(1){
                    pr=-k-1;
                    if(f[k]%2==0){
                        p.push({u[k],-k-1});
                        f[k]++;
                        if(x[k]==-k-1){
                            x[k]=0;
                            break;
                        }else if(x[k]<0){
                            k=-x[k]-1;
                        }else{
                            h++;
                            f[h-1]=1;
                            x.pb(-h);
                            y.pb(-h);
                            x[h-1]=x[k];
                            x[k]=-h;
                            k=h-1;
                        }
                    }else{
                        f[k]++;
                        if(y[k]==-k-1){
                            y[k]=0;
                            break;
                        }else if(y[k]<0){
                            k=-y[k]-1;
                        }else{
                            h++;
                            f[h-1]=1;
                            x.pb(-h);
                            y.pb(-h);
                            x[h-1]=y[k];
                            y[k]=-h;
                            k=h-1;
                        }
                    }
                }
            }
        }
    }
    //cout<<c.size()<<" "<<x.size()<<" "<<y.size()<<endl;
    for(int i=0;i<=M;i++){
       // cout<<i<<" "<<c[i]<<endl;
    }
    for(int i=0;i<x.size();i++){
       //if(x[i]==-i-1)swap(x[i],y[i]);
       //cout<<-i-1<<" "<<x[i]<<" "<<y[i]<<endl;
    }
    if(h>2*A.size()-2)exit(1);
    answer(c,x,y);
    return ;
}

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:22:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for(int i=0;i<A.size()-1;i++){
      |                 ~^~~~~~~~~~~
doll.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |             for(int j=0;j<v[i].size();j++){
      |                         ~^~~~~~~~~~~~
doll.cpp:90:34: error: 'i' was not declared in this scope
   90 |                 if(u[-k-1]==0)u[-i-1]=r;
      |                                  ^
doll.cpp:92:32: error: 'i' was not declared in this scope
   92 |                     p.push({u[-i-1],k});
      |                                ^
doll.cpp:92:39: error: no matching function for call to 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >::push(<brace-enclosed initializer list>)'
   92 |                     p.push({u[-i-1],k});
      |                                       ^
In file included from /usr/include/c++/10/queue:64,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:86,
                 from doll.cpp:2:
/usr/include/c++/10/bits/stl_queue.h:640:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(const value_type&) [with _Tp = std::pair<int, int>; _Sequence = std::vector<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, int>]'
  640 |       push(const value_type& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:640:30: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'const value_type&' {aka 'const std::pair<int, int>&'}
  640 |       push(const value_type& __x)
      |            ~~~~~~~~~~~~~~~~~~^~~
/usr/include/c++/10/bits/stl_queue.h:648:7: note: candidate: 'void std::priority_queue<_Tp, _Sequence, _Compare>::push(std::priority_queue<_Tp, _Sequence, _Compare>::value_type&&) [with _Tp = std::pair<int, int>; _Sequence = std::vector<std::pair<int, int> >; _Compare = std::greater<std::pair<int, int> >; std::priority_queue<_Tp, _Sequence, _Compare>::value_type = std::pair<int, int>]'
  648 |       push(value_type&& __x)
      |       ^~~~
/usr/include/c++/10/bits/stl_queue.h:648:25: note:   no known conversion for argument 1 from '<brace-enclosed initializer list>' to 'std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >::value_type&&' {aka 'std::pair<int, int>&&'}
  648 |       push(value_type&& __x)
      |            ~~~~~~~~~~~~~^~~
doll.cpp:103:19: error: 'class std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >' has no member named 'begin'
  103 |         reverse(p.begin(),p.end());
      |                   ^~~~~
doll.cpp:103:29: error: 'class std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >' has no member named 'end'
  103 |         reverse(p.begin(),p.end());
      |                             ^~~
doll.cpp:104:31: error: no match for 'operator-' (operand type is 'const value_type' {aka 'const std::pair<int, int>'})
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                               ^~~~~~~~
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from doll.h:3,
                 from doll.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:500:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&)'
  500 |     operator-(const reverse_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:500:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::reverse_iterator<_Iterator>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:67,
                 from /usr/include/c++/10/vector:60,
                 from doll.h:3,
                 from doll.cpp:1:
/usr/include/c++/10/bits/stl_iterator.h:1533:5: note: candidate: 'template<class _IteratorL, class _IteratorR> constexpr decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&)'
 1533 |     operator-(const move_iterator<_IteratorL>& __x,
      |     ^~~~~~~~
/usr/include/c++/10/bits/stl_iterator.h:1533:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::move_iterator<_IteratorL>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from doll.cpp:2:
/usr/include/c++/10/complex:361:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const std::complex<_Tp>&, const std::complex<_Tp>&)'
  361 |     operator-(const complex<_Tp>& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:361:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::complex<_Tp>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from doll.cpp:2:
/usr/include/c++/10/complex:370:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const std::complex<_Tp>&, const _Tp&)'
  370 |     operator-(const complex<_Tp>& __x, const _Tp& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:370:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::complex<_Tp>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from doll.cpp:2:
/usr/include/c++/10/complex:379:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const _Tp&, const std::complex<_Tp>&)'
  379 |     operator-(const _Tp& __x, const complex<_Tp>& __y)
      |     ^~~~~~~~
/usr/include/c++/10/complex:379:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   candidate expects 2 arguments, 1 provided
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from doll.cpp:2:
/usr/include/c++/10/complex:456:5: note: candidate: 'template<class _Tp> std::complex<_Tp> std::operator-(const std::complex<_Tp>&)'
  456 |     operator-(const complex<_Tp>& __x)
      |     ^~~~~~~~
/usr/include/c++/10/complex:456:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::complex<_Tp>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from doll.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom1, class _Dom2> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Expr, _Dom1, _Dom2>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::_Expr<_Dom2, typename _Dom2::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from doll.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_Constant, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const typename _Dom::value_type&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from doll.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Constant, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const typename _Dom::value_type&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   candidate expects 2 arguments, 1 provided
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from doll.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Expr, std::_ValArray, _Dom, typename _Dom::value_type>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::_Expr<_Dom1, typename _Dom1::value_type>&, const std::valarray<typename _Dom::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::_Expr<_Dom1, typename _Dom1::value_type>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/c++/10/valarray:603,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from doll.cpp:2:
/usr/include/c++/10/bits/valarray_after.h:406:5: note: candidate: 'template<class _Dom> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_Expr, typename _Dom::value_type, _Dom>, typename std::__fun<std::__minus, typename _Dom1::value_type>::result_type> std::operator-(const std::valarray<typename _Dom::value_type>&, const std::_Expr<_Dom1, typename _Dom1::value_type>&)'
  406 |     _DEFINE_EXPR_BINARY_OPERATOR(-, __minus)
      |     ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/valarray_after.h:406:5: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   candidate expects 2 arguments, 1 provided
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from doll.cpp:2:
/usr/include/c++/10/valarray:1186:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const std::valarray<_Tp>&, const std::valarray<_Tp>&)'
 1186 | _DEFINE_BINARY_OPERATOR(-, __minus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1186:1: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::valarray<_Tp>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from doll.cpp:2:
/usr/include/c++/10/valarray:1186:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_ValArray, std::_Constant, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const std::valarray<_Tp>&, const typename std::valarray<_Tp>::value_type&)'
 1186 | _DEFINE_BINARY_OPERATOR(-, __minus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1186:1: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   'const value_type' {aka 'const std::pair<int, int>'} is not derived from 'const std::valarray<_Tp>'
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from doll.cpp:2:
/usr/include/c++/10/valarray:1186:1: note: candidate: 'template<class _Tp> std::_Expr<std::__detail::_BinClos<std::__minus, std::_Constant, std::_ValArray, _Tp, _Tp>, typename std::__fun<std::__minus, _Tp>::result_type> std::operator-(const typename std::valarray<_Tp>::value_type&, const std::valarray<_Tp>&)'
 1186 | _DEFINE_BINARY_OPERATOR(-, __minus)
      | ^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/valarray:1186:1: note:   template argument deduction/substitution failed:
doll.cpp:104:38: note:   candidate expects 2 arguments, 1 provided
  104 |         while(p.size()>0 && f[-p.top()-1]%2==0)p.pop();
      |                                      ^
doll.cpp:107:38: error: 'class std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >' has no member named 'back'
  107 |             while(p.size()>0 && f[-p.back()-1]%2==0)p.pop();
      |                                      ^~~~
doll.cpp:110:15: error: 'class std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, std::greater<std::pair<int, int> > >' has no member named 'pop_back'
  110 |             p.pop_back();
      |               ^~~~~~~~
doll.cpp:165:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |     for(int i=0;i<x.size();i++){
      |                 ~^~~~~~~~~
doll.cpp:169:9: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     if(h>2*A.size()-2)exit(1);
      |        ~^~~~~~~~~~~~~