Submission #1206864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206864		catling	Aliens (IOI16_aliens)	C++20	Compilation error	0 ms	0 KiB

aliens

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

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    using ll = long long;
    const ll INF = (ll)1e18;
    const ll N = n;

    std::vector<std::pair<int,int>> pts(n);
    for(int i=0; i<n; ++i) {
        pts[i] = { std::min(r[i],c[i]), std::max(r[i],c[i]) };
    }
    std::sort(pts.begin(), pts.end());

    std::vector<ll> A(n+1), B(n+1);
    for(int i=1; i<=n; ++i) {
        A[i] = pts[i-1].first;
        B[i] = pts[i-1].second;
    }

    std::vector<ll> seg(4*(n+1), -INF);
    auto build = [&](auto&& self, int idx, int L, int R) -> void {
        if(L==R) {
            seg[idx] = B[L];
        } else {
            int M = (L+R)/2;
            self(self, idx*2, L, M);
            self(self, idx*2+1, M+1, R);
            seg[idx] = std::max(seg[idx*2], seg[idx*2+1]);
        }
    };
    build(build,1,1,n);

    auto query = [&](auto&& self, int idx, int L, int R, int ql, int qr)->ll {
        if(qr<L||R<ql) return -INF;
        if(ql<=L&&R<=qr) return seg[idx];
        int M=(L+R)/2;
        return std::max(self(self,idx*2,L,M,ql,qr),
                        self(self,idx*2+1,M+1,R,ql,qr));
    };

    std::vector<ll> dp(n+1), best(n+1);
    std::vector<int> cnt(n+1), bestCnt(n+1);
    ll lambda=0;

    auto solveDC = [&](auto&& self, int L, int R, int optL, int optR) -> void {
        if(L>R) return;
        int mid=(L+R)/2;
        ll val=INF; int bk=-1, bc=0;
        for(int j=optL; j<=std::min(optR,mid-1); ++j) {
            ll mx = query(query,1,1,n,j+1,mid);
            ll len = mx - A[j+1] + 1;
            ll cost = len*len + lambda;
            ll cand = dp[j] + cost;
            int cc = cnt[j]+1;
            if(cand<val || (cand==val && cc<bc)) {
                val=cand; bc=cc; bk=j;
            }
        }
        best[mid]=val; bestCnt[mid]=bc;
        self(self, L, mid-1, optL, bk);
        self(self, mid+1, R, bk, optR);
    };

    auto runWith = [&](ll lam){
        lambda=lam;
        dp.assign(n+1, INF);
        cnt.assign(n+1, 0);
        dp[0]=0; cnt[0]=0;
        solveDC(solveDC,1,n,0,n-1);
        return std::make_pair(best[n], bestCnt[n]);
    };

    ll lo=0, hi=4LL*m*m+10;
    while(lo<hi) {
        ll mid=(lo+hi)/2;
        auto [v,c]=runWith(mid);
        if(c>k) lo=mid+1;
        else hi=mid;
    }

    auto [v,c] = runWith(lo);
    return v - lo*c;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:84:13: error: declaration of 'auto c' shadows a parameter
   84 |     auto [v,c] = runWith(lo);
      |             ^
aliens.cpp:6:81: note: 'std::vector<int> c' previously declared here
    6 | long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
      |                                                                ~~~~~~~~~~~~~~~~~^
aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~