Submission #648046

#	Time	Username	Problem	Language	Result	Execution time	Memory
648046		ghostwriter	Aliens (IOI16_aliens)	C++14	0 / 100	1 ms	340 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include <debug.h>
#include "grader.cpp"
#else
#define debug(...)
#endif
#define ft front
#define bk back
#define st first
#define nd second
#define ins insert
#define ers erase
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define bg begin
#define ed end
#define all(x) (x).bg(), (x).ed()
#define sz(x) (int)(x).size()
typedef long long ll; typedef unsigned long long ull;
typedef double db; typedef long double ldb;
typedef pair<int, int> pi; typedef pair<ll, ll> pll;
typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pi> vpi; typedef vector<pll> vpll;
typedef string str;
template<typename T> T gcd(T a, T b) { return (b == 0? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))
#define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
#define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define FSN(i, n) for (int (i) = (n) - 1; (i) >= 0; --(i))
#define EACH(i, x) for (auto &(i) : (x))
#define WHILE while
#define file "TEST"
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
/*
----------------------------------------------------------------
    END OF TEMPLATE
----------------------------------------------------------------
    Tran The Bao - ghostwriter
    Training for VOI23 gold medal
----------------------------------------------------------------
    DIT ME CHUYEN BAO LOC
----------------------------------------------------------------
*/
namespace subtask123 {
    const int oo = 1e9 + 5;
    const int M = 1001;
    int f[M][M], d[M][M], d1[M][M], rs = oo;
    int get(int x1, int y1, int x2, int y2) {
        if (x1 > x2 || y1 > y2) return 0;
        return f[x2][y2] - (x1? f[x1 - 1][y2] : 0) - (y1? f[x2][y1 - 1] : 0) + (x1 && y1? f[x1 - 1][y1 - 1] : 0);
    }
    ll take_photos(int n, int m, int k, vi r, vi c) {
        FRN(i, n) ++f[r[i]][c[i]];
        FRN(i, m)
        FRN(j, m)
            f[i][j] += (j? f[i][j - 1] : 0) + (i? f[i - 1][j] : 0) - (i && j? f[i - 1][j - 1] : 0);
        FRN(i, m)
        FRN(j, m) {
            d1[i][j] = oo;
            FOS(z, m - 1, i) {
                int pre = get(j, j, m - 1, m - 1), cur = get(i, i, z, z);
                int uni = get(j, j, z, z);
                int total = get(i, i, m - 1, m - 1);
                if (cur + pre - uni == total) d1[i][j] = z;
            }
            // debug(i, j, d1[i][j]);
        }
        FRN(i, m)
        FRN(j, k) {
            d[i][j] = oo;
            if (j) {
                FRN(z, i)
                    if (d1[z][i] != oo) {
                        int len = d1[z][i] - z + 1;
                        int len1 = max(0, min(d1[i][m - 1] - i + 1, d1[z][i] - i + 1));
                        d[i][j] = min(d[i][j], len * len - len1 * len1 + d[z][j - 1]);
                        // debug(i, j, z, len, len * len - len1 * len1 + d[z][j - 1]);
                    }
            }
            int pre = get(i, i, m - 1, m - 1), cur = get(0, 0, m - 1, m - 1);
            if (pre == cur) d[i][j] = min(d[i][j], 0);
        }
        FRN(i, m) {
            int len;
            if (d1[i][m - 1] < oo) len = d1[i][m - 1] - i + 1;
            else len = m - i;
            rs = min(rs, len * len + d[i][k - 1]);
            // debug(i, len, d[i][k - 1]);
        }
        return rs;
    }
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    if (n <= 500 && m <= 1000) return subtask123::take_photos(n, m, k, r, c);
    return 0;
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6

2 6 2
1 4
4 1
----------------------------------------------------------------
From Benq:
    stuff you should look for
        * int overflow, array bounds
        * special cases (n=1?)
        * do smth instead of nothing and stay organized
        * WRITE STUFF DOWN
        * DON'T GET STUCK ON ONE APPROACH
----------------------------------------------------------------
*/

Compilation message (stderr)

aliens.cpp: In function 'll subtask123::take_photos(int, int, int, vi, vi)':
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
aliens.cpp:62:9: note: in expansion of macro 'FRN'
   62 |         FRN(i, n) ++f[r[i]][c[i]];
      |         ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
aliens.cpp:63:9: note: in expansion of macro 'FRN'
   63 |         FRN(i, m)
      |         ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
aliens.cpp:64:9: note: in expansion of macro 'FRN'
   64 |         FRN(j, m)
      |         ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
aliens.cpp:66:9: note: in expansion of macro 'FRN'
   66 |         FRN(i, m)
      |         ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
aliens.cpp:67:9: note: in expansion of macro 'FRN'
   67 |         FRN(j, m) {
      |         ^~~
aliens.cpp:35:31: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   35 | #define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))
      |                               ^
aliens.cpp:69:13: note: in expansion of macro 'FOS'
   69 |             FOS(z, m - 1, i) {
      |             ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
aliens.cpp:77:9: note: in expansion of macro 'FRN'
   77 |         FRN(i, m)
      |         ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
aliens.cpp:78:9: note: in expansion of macro 'FRN'
   78 |         FRN(j, k) {
      |         ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'z' [-Wparentheses]
   36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
aliens.cpp:81:17: note: in expansion of macro 'FRN'
   81 |                 FRN(z, i)
      |                 ^~~
aliens.cpp:36:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   36 | #define FRN(i, n) for (int (i) = 0; (i) < (n); ++(i))
      |                            ^
aliens.cpp:92:9: note: in expansion of macro 'FRN'
   92 |         FRN(i, m) {
      |         ^~~

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