제출 #579391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
579391		perchuts	Aliens (IOI16_aliens)	C++17	컴파일 에러	0 ms	0 KiB

aliens

#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define endl '\n'
#define pb push_back
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define f first
#define s second
using namespace std;
#include "aliens.h"
using ll = long long;

template<typename X, typename Y> bool ckmin(X& x, const Y& y) { return (y < x) ? (x=y,1):0; }
template<typename X, typename Y> bool ckmax(X& x, const Y& y) { return (x < y) ? (x=y,1):0; }

vector<pair<ll,ll>>pareto;

ll eval(pair<ll,ll>x,ll y){return x.f*y + x.s;}
ll sq(ll x){return x*x;}

bool cross(pair<ll,ll>back,pair<ll,ll>mid,pair<ll,ll>front){
    return (back.s-mid.s)*(front.f-mid.f)>(back.f-mid.f)*(front.s-mid.s);
}

pair<ll,ll> solve(ll lambda){
    //CHT
    deque<pair<pair<ll,ll>,ll>>lines={{{-2*pareto[0].f,sq(pareto[0].f)},0}};
    int n = sz(pareto);
    for(int i=0;i<n;++i){
        auto [x,y] = pareto[i];++y;
        while(sz(lines)>=2&&eval(lines[0].f,y)>eval(lines[1].f,y))lines.pop_front();
        ll dpi = eval(lines[0].f,y) + sq(y) + lambda, qnt = lines[0].s+1;
        if(i==n-1)return {dpi,qnt};
        else{
            dpi += sq(pareto[i+1].f) - sq(max(0ll,y-pareto[i+1].f));
            pair<ll,ll>cur = {-2*pareto[i+1].f,dpi};
            while(sz(lines)>=2&& cross(lines[sz(lines)-2].f,lines.back().f,cur))lines.pop_back();
            lines.pb({cur,qnt});
        }
    }
    return {0,0};
}

ll take_photos(int n, int m, int k, vector<int> r1, vector<int> c) {
    vector<ii>v(n);
    for(int i=0;i<n;++i){  
        if(r1[i]<=c[i])v[i] = {r1[i],c[i]};
        else v[i] = {c[i],r1[i]};
    }
    sort(all(v));
    for(int i=0;i<n;++i){
        if(pareto.empty()||pareto.back().second<v[i].s){
            if(!pareto.empty()&&pareto.back().first==v[i].f)pareto.pop_back();
            pareto.push_back(v[i]);
        }
    }
    //Lagrange opt.
    ll l = 0, r = 1e12;//max delta = 1e12 porque m<=1e6, logo lambda <= 1e12
    while(l<r){
        ll md = (l+r)/2;
        pair<ll,ll>cur = solve(md);
        if(cur.s>k)l = md+1ll;
        else r = md;
    }   
    pair<ll,ll>res = solve(r);
    ll ans = res.f - r*k;
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:45:12: error: 'ii' was not declared in this scope
   45 |     vector<ii>v(n);
      |            ^~
aliens.cpp:45:14: error: template argument 1 is invalid
   45 |     vector<ii>v(n);
      |              ^
aliens.cpp:45:14: error: template argument 2 is invalid
aliens.cpp:47:25: error: invalid types 'int[int]' for array subscript
   47 |         if(r1[i]<=c[i])v[i] = {r1[i],c[i]};
      |                         ^
aliens.cpp:48:15: error: invalid types 'int[int]' for array subscript
   48 |         else v[i] = {c[i],r1[i]};
      |               ^
aliens.cpp:2:18: error: request for member 'begin' in 'v', which is of non-class type 'int'
    2 | #define all(x) x.begin(), x.end()
      |                  ^~~~~
aliens.cpp:50:10: note: in expansion of macro 'all'
   50 |     sort(all(v));
      |          ^~~
aliens.cpp:2:29: error: request for member 'end' in 'v', which is of non-class type 'int'
    2 | #define all(x) x.begin(), x.end()
      |                             ^~~
aliens.cpp:50:10: note: in expansion of macro 'all'
   50 |     sort(all(v));
      |          ^~~
aliens.cpp:52:50: error: invalid types 'int[int]' for array subscript
   52 |         if(pareto.empty()||pareto.back().second<v[i].s){
      |                                                  ^
aliens.cpp:53:55: error: invalid types 'int[int]' for array subscript
   53 |             if(!pareto.empty()&&pareto.back().first==v[i].f)pareto.pop_back();
      |                                                       ^
aliens.cpp:54:31: error: invalid types 'int[int]' for array subscript
   54 |             pareto.push_back(v[i]);
      |                               ^