제출 #158024

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

aliens

#include "aliens.h"
#include <vector>
#include <iostream>
#include <deque>
#include <algorithm>

#define int int64_t

using namespace std;

struct solver
{
    vector<int> l;
    vector<int> r;
    int k;
    int n;
    int m;
    vector<int> overlap;

    pair<int,int> run(int c)
    {
        deque<pair<int,int>> q;
        vector<int> ks(n + 1, 0);
        vector<int> dp(n + 1, 0);
        int ck = 0;
        for (int i = 1; i <= n; i++)
        {
            int a = -2*l[i - 1];
            int b = dp[i - 1] - 2*l[i - 1] + l[i - 1]*l[i - 1] - overlap[i - 1];
            q.push_back({a, b});
            int rv = r[i - 1];
            while (q.size() > 1)
            {
                int v0 = q[0].first * rv + q[0].second;
                int v1 = q[1].first * rv + q[1].second;
                if (v1 < v0)
                {
                    ck++;
                    q.pop_front();
                }
                else
                {
                    break;
                }
            }
            ks[i] = ks[ck] + 1;
            dp[i] = q[0].first * rv + q.front().second + c + r[i - 1]*r[i - 1] + 2*r[i - 1] + 1;
        }
        return {ks[n], dp[n]};
    }

    int solve()
    {
        overlap.resize(n, 0);
        for (int i = 1; i < n; i++)
        {
            if (r[i - 1] >= l[i])
            {
                overlap[i] = (r[i - 1] - l[i] + 1)*(r[i - 1] - l[i] + 1);
            }
        }

        int bl = 0;
        int br = m*m;
        while (br - bl > 1)
        {
            int m = (bl + br)/2;
            if (run(m).first < k)
            {
                br = m;
            }
            else
            {
                bl = m;
            }
        }
        auto fin = run(bl);
        return fin.second - bl*fin.first;
    }
};

int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c)
{
    vector<pair<int,int>> intervals;
    for (int i = 0; i < n; i++)
    {
        intervals.push_back({min(r[i], c[i]), -max(r[i], c[i])});
    }
    sort(intervals.begin(), intervals.end());
    vector<int> nl;
    vector<int> nr;
    int mmx = -1;
    for (int i = 0; i < n; i++)
    {
        if (-intervals[i].second > mmx)
        {
            nl.push_back(intervals[i].first);
            nr.push_back(-intervals[i].second);
            mmx = -intervals[i].second;
        }
    }
    int nn = nl.size();
    solver s;
    s.l = nl;
    s.r = nr;
    s.k = k;
    s.n = nn;
    s.m = m;
    return s.solve();
}

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

aliens.cpp: In function 'int64_t take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:82:5: error: ambiguating new declaration of 'int64_t take_photos(int, int, int, std::vector<int>, std::vector<int>)'
 int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c)
     ^~~~~~~~~~~
In file included from aliens.cpp:1:0:
aliens.h:5:11: note: old declaration 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)'
 long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c);
           ^~~~~~~~~~~