Submission #599519

#	Time	Username	Problem	Language	Result	Execution time	Memory
599519		jophyyjh	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	308 KiB

aliens

/**
 * I don't feel like fully solving this, so maybe i'll just score some partials.
 * 
 * [S1] Too trivial
 * [S2] Each point lies on the main diagonal. Clearly, no two squares should have
 *      common squares, which means the points are partitioned into contiguous
 *      segments. O(n^2 * k) dp kills it.
 * [S3] Maybe we can somehow sort the points based on their columns, then apply [S2]?
 *      Yep, pretty much analagous to [S2]. The key here is that if (2,5), (3,5),
 *      the square that covers (2,5) must cover (3,5).
 *      Well, i really shouldn't have written "Too trivial" in [S1]. The following
 *      observation is:     if two segments (a1,b1) (a2,b2) satisfy a1 <= a2 and
 *      b1 >= b2, the former's square completely contains the latter, so we shall
 *      remove the latter. This means when we sort the points based on their b
 *      values, a values are strictly increasing.
 *      So in fact, [S3] = [S1] + [S2]!
 * 
 * Time Complexity: O(n^2 * k)
 * Implementation 1.2   (only S1 fully solved)
*/

#include <bits/stdc++.h>
#include "aliens.h"

typedef long long   ll;

const int N_MAX = 500;
const ll INF = 0x3f3f3f3f;

inline ll sqr(int k)    { return ll(k) * ll(k); }


ll cover[N_MAX + 1][N_MAX + 1];

struct point_t {
    int i, j;
};

inline bool operator==(const point_t& p1, const point_t& p2)    { return p1.i == p2.i && p1.j == p2.j; }

ll take_photos(int n, int m, int max_sqr, std::vector<int> row, std::vector<int> col) {
    if (max_sqr != n)
        return -1;      // bye
    std::vector<point_t> values(n);
    for (int k = 0; k < n; k++)
        values[k].i = std::min(row[k], col[k]), values[k].j = std::max(row[k], col[k]);
    std::sort(values.begin(), values.end(),
              [](const point_t& p1, const point_t& p2) {
                  return p1.j < p2.j || (p1.j == p2.j && p1.i > p2.i);
              });
    
    std::vector<bool> skipped(n, false);
    for (int k = n - 1, suffix_min = INF; k >= 0; k--) {
        if (values[k].i >= suffix_min)
            skipped[k] = true;
        suffix_min = std::min(suffix_min, values[k].i);
    }
    ll area = 0;
    for (int k = 0, prev = -1; k < n; k++) {
        if (skipped[k])
            continue;
        area += sqr(values[k].j - values[k].i + 1)
                    - sqr(std::max(prev - values[k].i + 1, 0));
        prev = values[k].j;
    }
    return area;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40