Submission #1243446

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243446		aykhn	Nile (IOI24_nile)	C++20	Compilation error	0 ms	0 KiB

nile

#include "nile.h"
#include <vector>
#include <algorithm>
#include <limits>

using ll = long long;
static const ll NEG_INF = std::numeric_limits<ll>::min() / 4;

// 2x2 max-plus matrix
struct Mat {
    ll a[2][2];
};

// Max-plus multiplication: C = B * A
static Mat mmul(const Mat &B, const Mat &A) {
    Mat C;
    for(int i = 0; i < 2; i++) {
        for(int j = 0; j < 2; j++) {
            ll v = NEG_INF;
            for(int k = 0; k < 2; k++) {
                v = std::max(v, B.a[i][k] + A.a[k][j]);
            }
            C.a[i][j] = v;
        }
    }
    return C;
}

std::vector<long long> calculate_costs(
    std::vector<int> W, std::vector<int> A,
    std::vector<int> B, std::vector<int> E) {
    int N = W.size(), Q = E.size();
    
    // base sum
    long long sumA = 0;
    for(int i = 0; i < N; i++) sumA += A[i];
    if(N == 1) return std::vector<ll>(Q, sumA);

    // sort items by weight
    struct It{int w, idx;};
    std::vector<It> it(N);
    for(int i=0;i<N;i++) it[i]={W[i],i};
    std::sort(it.begin(), it.end(),[](auto &x,auto &y){return x.w<y.w;});
    
    // compute gaps
    std::vector<pair<int,int>> gaps;
    for(int k=1;k<N;k++) gaps.emplace_back(it[k].w - it[k-1].w, k);
    std::sort(gaps.begin(), gaps.end());

    // queries sorted
    vector<pair<int,int>> qs(Q);
    for(int i=0;i<Q;i++) qs[i]={E[i],i};
    sort(qs.begin(), qs.end());
    
    // DSU
    vector<int> p(N), sz(N,1);
    vector<long long> sumd(N), mind(N);
    for(int i=0;i<N;i++){
        p[i]=i;
        sumd[i] = (long long)A[it[i].idx] - B[it[i].idx];
        mind[i] = sumd[i];
    }
    function<int(int)> find=[&](int x){return p[x]==x?x:p[x]=find(p[x]);};
    auto comp_val=[&](int r)->long long{
        // matched sum in component: if size even sumd, else sumd - mind
        if(sz[r]%2==0) return sumd[r];
        else return sumd[r] - mind[r];
    };
    long long matched=0;
    // initially no matches
    
    vector<long long> ans(Q);
    int ptr=0;
    for(auto &qr:qs){
        int D=qr.first, qi=qr.second;
        while(ptr<(int)gaps.size() && gaps[ptr].first<=D){
            int k=gaps[ptr].second;
            int u = find(k-1), v = find(k);
            if(u!=v){
                // remove old contributions
                matched -= comp_val(u);
                matched -= comp_val(v);
                // unify
                p[v]=u;
                sz[u]+=sz[v];
                sumd[u]+=sumd[v];
                mind[u]=min(mind[u], mind[v]);
                // add new
                matched += comp_val(u);
            }
            ptr++;
        }
        ans[qi] = sumA - matched;
    }
    return ans;
}

Compilation message (stderr)

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:46:17: error: 'pair' was not declared in this scope; did you mean 'std::pair'?
   46 |     std::vector<pair<int,int>> gaps;
      |                 ^~~~
      |                 std::pair
In file included from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/vector:60,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_pair.h:211:12: note: 'std::pair' declared here
  211 |     struct pair
      |            ^~~~
nile.cpp:46:29: error: template argument 1 is invalid
   46 |     std::vector<pair<int,int>> gaps;
      |                             ^~
nile.cpp:46:29: error: template argument 2 is invalid
nile.cpp:47:31: error: request for member 'emplace_back' in 'gaps', which is of non-class type 'int'
   47 |     for(int k=1;k<N;k++) gaps.emplace_back(it[k].w - it[k-1].w, k);
      |                               ^~~~~~~~~~~~
nile.cpp:48:20: error: request for member 'begin' in 'gaps', which is of non-class type 'int'
   48 |     std::sort(gaps.begin(), gaps.end());
      |                    ^~~~~
nile.cpp:48:34: error: request for member 'end' in 'gaps', which is of non-class type 'int'
   48 |     std::sort(gaps.begin(), gaps.end());
      |                                  ^~~
nile.cpp:51:5: error: 'vector' was not declared in this scope
   51 |     vector<pair<int,int>> qs(Q);
      |     ^~~~~~
nile.cpp:51:5: note: suggested alternatives:
In file included from /usr/include/c++/11/vector:67,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_vector.h:389:11: note:   'std::vector'
  389 |     class vector : protected _Vector_base<_Tp, _Alloc>
      |           ^~~~~~
In file included from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/11/vector:86:13: note:   'std::pmr::vector'
   86 |       using vector = std::vector<_Tp, polymorphic_allocator<_Tp>>;
      |             ^~~~~~
nile.cpp:51:17: error: expected primary-expression before 'int'
   51 |     vector<pair<int,int>> qs(Q);
      |                 ^~~
nile.cpp:52:26: error: 'qs' was not declared in this scope
   52 |     for(int i=0;i<Q;i++) qs[i]={E[i],i};
      |                          ^~
nile.cpp:53:10: error: 'qs' was not declared in this scope
   53 |     sort(qs.begin(), qs.end());
      |          ^~
nile.cpp:53:5: error: 'sort' was not declared in this scope
   53 |     sort(qs.begin(), qs.end());
      |     ^~~~
nile.cpp:53:5: note: suggested alternatives:
In file included from /usr/include/c++/11/algorithm:74,
                 from nile.cpp:3:
/usr/include/c++/11/pstl/glue_algorithm_defs.h:296:1: note:   'std::sort'
  296 | sort(_ExecutionPolicy&& __exec, _RandomAccessIterator __first, _RandomAccessIterator __last);
      | ^~~~
In file included from /usr/include/c++/11/algorithm:64,
                 from nile.cpp:3:
/usr/include/c++/11/bits/ranges_algo.h:1834:30: note:   'std::ranges::sort'
 1834 |   inline constexpr __sort_fn sort{};
      |                              ^~~~
nile.cpp:56:12: error: expected primary-expression before 'int'
   56 |     vector<int> p(N), sz(N,1);
      |            ^~~
nile.cpp:57:12: error: expected primary-expression before 'long'
   57 |     vector<long long> sumd(N), mind(N);
      |            ^~~~
nile.cpp:59:9: error: 'p' was not declared in this scope
   59 |         p[i]=i;
      |         ^
nile.cpp:60:9: error: 'sumd' was not declared in this scope; did you mean 'sumA'?
   60 |         sumd[i] = (long long)A[it[i].idx] - B[it[i].idx];
      |         ^~~~
      |         sumA
nile.cpp:61:9: error: 'mind' was not declared in this scope
   61 |         mind[i] = sumd[i];
      |         ^~~~
nile.cpp:63:5: error: 'function' was not declared in this scope; did you mean 'std::function'?
   63 |     function<int(int)> find=[&](int x){return p[x]==x?x:p[x]=find(p[x]);};
      |     ^~~~~~~~
      |     std::function
In file included from /usr/include/c++/11/functional:59,
                 from /usr/include/c++/11/pstl/glue_algorithm_defs.h:13,
                 from /usr/include/c++/11/algorithm:74,
                 from nile.cpp:3:
/usr/include/c++/11/bits/std_function.h:111:11: note: 'std::function' declared here
  111 |     class function;
      |           ^~~~~~~~
nile.cpp:63:14: error: expected primary-expression before 'int'
   63 |     function<int(int)> find=[&](int x){return p[x]==x?x:p[x]=find(p[x]);};
      |              ^~~
nile.cpp: In lambda function:
nile.cpp:66:12: error: 'sz' was not declared in this scope
   66 |         if(sz[r]%2==0) return sumd[r];
      |            ^~
nile.cpp:66:31: error: 'sumd' was not declared in this scope; did you mean 'sumA'?
   66 |         if(sz[r]%2==0) return sumd[r];
      |                               ^~~~
      |                               sumA
nile.cpp:67:21: error: 'sumd' was not declared in this scope; did you mean 'sumA'?
   67 |         else return sumd[r] - mind[r];
      |                     ^~~~
      |                     sumA
nile.cpp:67:31: error: 'mind' was not declared in this scope
   67 |         else return sumd[r] - mind[r];
      |                               ^~~~
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:72:12: error: expected primary-expression before 'long'
   72 |     vector<long long> ans(Q);
      |            ^~~~
nile.cpp:76:29: error: request for member 'size' in 'gaps', which is of non-class type 'int'
   76 |         while(ptr<(int)gaps.size() && gaps[ptr].first<=D){
      |                             ^~~~
nile.cpp:76:43: error: invalid types 'int[int]' for array subscript
   76 |         while(ptr<(int)gaps.size() && gaps[ptr].first<=D){
      |                                           ^
nile.cpp:77:23: error: invalid types 'int[int]' for array subscript
   77 |             int k=gaps[ptr].second;
      |                       ^
nile.cpp:78:21: error: 'find' was not declared in this scope
   78 |             int u = find(k-1), v = find(k);
      |                     ^~~~
nile.cpp:78:21: note: suggested alternatives:
In file included from /usr/include/c++/11/algorithm:74,
                 from nile.cpp:3:
/usr/include/c++/11/pstl/glue_algorithm_defs.h:60:1: note:   'std::find'
   60 | find(_ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value);
      | ^~~~
In file included from /usr/include/c++/11/bits/ranges_algo.h:36,
                 from /usr/include/c++/11/algorithm:64,
                 from nile.cpp:3:
/usr/include/c++/11/bits/ranges_util.h:432:30: note:   'std::ranges::find'
  432 |   inline constexpr __find_fn find{};
      |                              ^~~~
nile.cpp:79:19: error: 'v' was not declared in this scope
   79 |             if(u!=v){
      |                   ^
nile.cpp:84:17: error: 'p' was not declared in this scope
   84 |                 p[v]=u;
      |                 ^
nile.cpp:85:17: error: 'sz' was not declared in this scope
   85 |                 sz[u]+=sz[v];
      |                 ^~
nile.cpp:86:17: error: 'sumd' was not declared in this scope; did you mean 'sumA'?
   86 |                 sumd[u]+=sumd[v];
      |                 ^~~~
      |                 sumA
nile.cpp:87:17: error: 'mind' was not declared in this scope
   87 |                 mind[u]=min(mind[u], mind[v]);
      |                 ^~~~
nile.cpp:87:25: error: 'min' was not declared in this scope
   87 |                 mind[u]=min(mind[u], mind[v]);
      |                         ^~~
nile.cpp:87:25: note: suggested alternatives:
In file included from /usr/include/c++/11/vector:62,
                 from nile.h:1,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   'std::min'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
In file included from /usr/include/c++/11/algorithm:64,
                 from nile.cpp:3:
/usr/include/c++/11/bits/ranges_algo.h:2957:29: note:   'std::ranges::min'
 2957 |   inline constexpr __min_fn min{};
      |                             ^~~
nile.cpp:93:9: error: 'ans' was not declared in this scope; did you mean 'abs'?
   93 |         ans[qi] = sumA - matched;
      |         ^~~
      |         abs
nile.cpp:93:13: error: 'qi' was not declared in this scope
   93 |         ans[qi] = sumA - matched;
      |             ^~
nile.cpp:95:12: error: 'ans' was not declared in this scope; did you mean 'abs'?
   95 |     return ans;
      |            ^~~
      |            abs