Submission #395363

#	Time	Username	Problem	Language	Result	Execution time	Memory
395363		blue	Aliens (IOI16_aliens)	C++17	Compilation error	0 ms	0 KiB

aliens

#include "aliens.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

/*
Cells (r, c) and (c, r) are equivalent.
(a, b) = (min(r, c), max(r, c))

A square (p, q) covers point (a, b) if and only if p <= a and b <= q

If (a1, b1) and (a2, b2) are points and a1 <= a2 and b2 <= b1, then (a2, b2) is irrelevant.
So, for any (a1, b1) and (a2, b2)   a1 < a2 <=> b1 < b2

When checking for overlapping areas, we only have to consider the last square.

Let points be sorted (a[1], b[1]) < (a[2], b[2]) < .... < (a[x], b[x]).

Let dp[i][k] be the minimum area required to cover the first i points using k squares.

dp[0][k] = 0
dp[i][k] = min{dp[j][k-1] + (b[i] - a[j] + 1)^2 - max(0, b[j] - a[j] + 1)^2 | j=1..i-1}

A point (a, b) requires a square of endpoints (a, a) and (b, b)  (side = b-a+1)



dp[j][x-1] + sq(b[i]-a[j+1])
dp[j][x-1] + b[i]^2 + a[j+1]^2 - 2*b[i]*a[j+1]
1*[[dp[j][x-1] + a[j+1]^2]] + (-2*b[i])*[[ a[j+1] ]]
*/
vector<long long> a(1, -1), b(1, -1);

int N, M, K;
vector<long long> A, B;

long long sq(long long x)
{
    return x*x;
}

const long long INF = 5'000'000'000'000; //CHANGE!!!!!!!!!



long long parametric_search(long long X, long long Y)
{
    cerr << "search " << X << ' ' << Y << '\n';
    long long CT = (X + Y)/2;
    // if(X != Y) CT++;

    cerr << "ct = " << CT << '\n';

    long long dp[N+1]; // minimum area+cost to cover first i points
    int photos[N+1];

    dp[0] = photos[0] = 0;

    dp[1] = sq(B[1] - A[1]) + CT;
    photos[1] = 1;
    for(int i = 2; i <= N; i++)
    {
        int J = -1;
        long long opt = INF;

        for(int j = 0; j < i; j++)
        {
            long long val;
            if(B[j] - A[i] + 1 >= 1)
                val = CT + dp[j] + sq(B[i] - A[j+1]) - sq(B[j] - A[i]);
            else
                val = CT + dp[j] + sq(B[i] - A[j+1]);

            if(val < opt)
            {
                opt = val;
                J = j;
            }
        }

        dp[i] = opt;
        photos[i] = photos[J] + 1;
    }

    // for(int i = 1; i <= N; i++) cerr << dp[i] << ' ';
    // cerr << '\n';
    // for(int i = 1; i <= N; i++) cerr << photos[i] << ' ';
    // cerr << '\n';

    if(X == Y) return dp[N] - CT * photos[N];
    else
    {
        if(photos[N] <= K)
            return parametric_search(X, CT);
        else return parametric_search(CT+1, Y);
    }
}



long long take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    // cerr << '\n';
    N = n;
    M = m;
    K = k;

    int I[n];
    for(int i = 0; i < n; i++)
        I[i] = i;

    sort(I, I+n, [] (int x, int y)
    {
        if(min(R[x], C[x]) == min(R[y], C[y]))
            return max(R[x], C[x]) > max(R[y], C[y]);
        return min(R[x], C[x]) < min(R[y], C[y]);
    });

    int maxb = -1;

    for(int i:I)
    {
        // cerr << i << ' ';
        if(maxb < max(r[i], c[i]))
        {
            maxb = max(r[i], c[i]);
            a.push_back(min(r[i], c[i]));
            b.push_back(max(r[i], c[i]) + 1);
        }
    }

    n = a.size() - 1;
    // for(int i = 1; i <= n; i++) cerr << a[i] << ' ' << b[i] << '\n';

    k = min(k, n);

    A = a;
    B = b;
    N = n;
    K = k;

    cerr << "points: \n";
    for(int i = 1; i <= N; i++) cerr << A[i] << ' ' << B[i] << '\n';

    cerr << "check\n";


    return parametric_search(0LL, INF);
}

Compilation message (stderr)

aliens.cpp: In lambda function:
aliens.cpp:115:16: error: 'R' was not declared in this scope
  115 |         if(min(R[x], C[x]) == min(R[y], C[y]))
      |                ^
aliens.cpp:115:22: error: 'C' was not declared in this scope
  115 |         if(min(R[x], C[x]) == min(R[y], C[y]))
      |                      ^
aliens.cpp:117:20: error: 'R' was not declared in this scope
  117 |         return min(R[x], C[x]) < min(R[y], C[y]);
      |                    ^
aliens.cpp:117:26: error: 'C' was not declared in this scope
  117 |         return min(R[x], C[x]) < min(R[y], C[y]);
      |                          ^
In file included from /usr/include/c++/9/bits/stl_algobase.h:71,
                 from /usr/include/c++/9/vector:60,
                 from aliens.h:3,
                 from aliens.cpp:1:
/usr/include/c++/9/bits/predefined_ops.h: In instantiation of 'constexpr bool __gnu_cxx::__ops::_Iter_comp_iter<_Compare>::operator()(_Iterator1, _Iterator2) [with _Iterator1 = int*; _Iterator2 = int*; _Compare = take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)>]':
/usr/include/c++/9/bits/stl_algo.h:81:17:   required from 'void std::__move_median_to_first(_Iterator, _Iterator, _Iterator, _Iterator, _Compare) [with _Iterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1920:34:   required from '_RandomAccessIterator std::__unguarded_partition_pivot(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1952:38:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int*; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1967:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:4899:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int*; _Compare = take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)>]'
aliens.cpp:118:6:   required from here
/usr/include/c++/9/bits/predefined_ops.h:143:18: error: void value not ignored as it ought to be
  143 |         { return bool(_M_comp(*__it1, *__it2)); }
      |                  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Val_comp_iter<_Compare>::operator()(_Value&, _Iterator) [with _Value = int; _Iterator = int*; _Compare = take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)>]':
/usr/include/c++/9/bits/stl_algo.h:1827:20:   required from 'void std::__unguarded_linear_insert(_RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Val_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1854:36:   required from 'void std::__insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1884:25:   required from 'void std::__final_insertion_sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1970:31:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:4899:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int*; _Compare = take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)>]'
aliens.cpp:118:6:   required from here
/usr/include/c++/9/bits/predefined_ops.h:215:11: error: void value not ignored as it ought to be
  215 |  { return bool(_M_comp(__val, *__it)); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/9/bits/predefined_ops.h: In instantiation of 'bool __gnu_cxx::__ops::_Iter_comp_val<_Compare>::operator()(_Iterator, _Value&) [with _Iterator = int*; _Value = int; _Compare = take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)>]':
/usr/include/c++/9/bits/stl_heap.h:133:48:   required from 'void std::__push_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare&) [with _RandomAccessIterator = int*; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_val<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_heap.h:237:23:   required from 'void std::__adjust_heap(_RandomAccessIterator, _Distance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = int*; _Distance = long int; _Tp = int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_heap.h:342:22:   required from 'void std::__make_heap(_RandomAccessIterator, _RandomAccessIterator, _Compare&) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1671:23:   required from 'void std::__heap_select(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1932:25:   required from 'void std::__partial_sort(_RandomAccessIterator, _RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1947:27:   required from 'void std::__introsort_loop(_RandomAccessIterator, _RandomAccessIterator, _Size, _Compare) [with _RandomAccessIterator = int*; _Size = long int; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:1967:25:   required from 'void std::__sort(_RandomAccessIterator, _RandomAccessIterator, _Compare) [with _RandomAccessIterator = int*; _Compare = __gnu_cxx::__ops::_Iter_comp_iter<take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)> >]'
/usr/include/c++/9/bits/stl_algo.h:4899:18:   required from 'void std::sort(_RAIter, _RAIter, _Compare) [with _RAIter = int*; _Compare = take_photos(int, int, int, std::vector<int>, std::vector<int>)::<lambda(int, int)>]'
aliens.cpp:118:6:   required from here
/usr/include/c++/9/bits/predefined_ops.h:177:11: error: void value not ignored as it ought to be
  177 |  { return bool(_M_comp(*__it, __val)); }
      |           ^~~~~~~~~~~~~~~~~~~~~~~~~~~