Submission #1219059

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219059		brinton	Fountain Parks (IOI21_parks)	C++20	Compilation error	0 ms	0 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int construct_roads(vector<int> x, vector<int> y) {
    int N = x.size();
    map<pair<int,int>,int> mp;
    for(int i = 0;i < N;i++) mp[{x[i],y[i]}] = i;
    vector<int> vis(N,false);

    int dx[4] = {0,2,-2,0};
    int dy[4] = {2,0,0,-2};
    vector<int> u,v,a,b;

    set<pair<int,int>> banned;
    function<bool(int,int)> add_road = [&](int aidx,int bidx){
        int midx = (x[aidx]+x[bidx])/2;
        int midy = (y[aidx]+y[bidx])/2;
        if(x[aidx] == x[bidx]){
            // vertical
            if((midy/2)%2 == (midx/2)%2){
                midx++;
            }else{
                midx--;
            }
        }else{
            // horizontal
            if((midx/2)%2 == (midy/2)%2){
                midy--;
            }else{
                midy++;
            }
        }

        if(banned.count({midx,midy})) return false;
        banned.insert({midx,midy});
        // {
        //     int nidx1 = -1,nidx2 = -1;
        //     for(int d = 0;d < 4;d++){
        //         int nx = midx+dx[d]/2;
        //         int ny = midy+dy[d]/2;
        //         if(nx == x[aidx] && ny == y[aidx]) continue;
        //         if(nx == x[bidx] && ny == y[bidx]) continue;
        //         if(mp.count({nx,ny})){
        //             if(nidx1 == -1) nidx1 = mp[{nx,ny}];
        //             else nidx2 = mp[{nx,ny}];
        //         }
        //     }
        //     if(nidx1 != -1 && nidx2 != -1){
        //         vis[nidx1] = true;
        //         vis[nidx2] = true;
        //         if(x[aidx] == x[nidx1] || y[aidx] == y[nidx1]){
        //             add_road(aidx,nidx1);
        //             add_road(bidx,nidx2);
        //         }else{
        //             add_road(aidx,nidx2);
        //             add_road(bidx,nidx1);
        //         }
        //     }
        // }

        u.push_back(aidx);
        v.push_back(bidx);
        a.push_back(midx);
        b.push_back(midy);
        return true;
    };

    auto doit = [&](int start){
        u.clear(),v.clear(),a.clear(),b.clear();
        banned.clear();
        vis = vector<int>(N,false);
        queue<int> q;
        q.push(start);
        while(!q.empty()){
            int idx = q.front();
            q.pop();
            vis[idx] = true;
            int cx = x[idx],cy = y[idx];
            for(int d = 0;d < 4;d++){
                int nx = cx+dx[d];
                int ny = cy+dy[d];
                if(!mp.count({nx,ny})) continue;
                int nidx = mp[{nx,ny}];
                if(vis[nidx]) continue;
                if(add_road(idx,nidx)) q.push(nidx);
            }
        }
    
        for(auto &i:vis){
            if(!i) return false;
        }
        build(u,v,a,b);
        return true;
    };

    vector<int> perm(N);
    for(int i = 0;i < N;i++) perm[i] = i;
    shuffle(perm.begin(),perm.end(),rng);
    for(int i = 0;i < min(perm.size(),3);i++){
        if(doit(perm[i])) return true;
    }
    return false;
}

Compilation message (stderr)

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:101:26: error: no matching function for call to 'min(std::vector<int>::size_type, int)'
  101 |     for(int i = 0;i < min(perm.size(),3);i++){
      |                       ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from parks.h:1,
                 from parks.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
parks.cpp:101:26: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
  101 |     for(int i = 0;i < min(perm.size(),3);i++){
      |                       ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:60,
                 from parks.h:1,
                 from parks.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
parks.cpp:101:26: note:   deduced conflicting types for parameter 'const _Tp' ('long unsigned int' and 'int')
  101 |     for(int i = 0;i < min(perm.size(),3);i++){
      |                       ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from parks.h:1,
                 from parks.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
parks.cpp:101:26: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  101 |     for(int i = 0;i < min(perm.size(),3);i++){
      |                       ~~~^~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/vector:62,
                 from parks.h:1,
                 from parks.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
parks.cpp:101:26: note:   mismatched types 'std::initializer_list<_Tp>' and 'long unsigned int'
  101 |     for(int i = 0;i < min(perm.size(),3);i++){
      |                       ~~~^~~~~~~~~~~~~~~