Submission #1232623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232623		asdfgrace	Portal (BOI24_portal)	C++20	1 / 100	11 ms	1096 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) //x
#define prt(x) dbg(cerr << x)
#define pv(x) dbg(cerr << #x << " = " << x << '\n')
#define parr(x) dbg(cerr << #x << " = "; for (auto y : x) {cerr << y << ' ';} cerr << '\n';)
#define parr2d(x) dbg(cerr << #x << " = \n"; for (auto _ : x) {parr(_);} cerr << '\n';)

/*
if there are no portals you can use an infinite # of colors
if there are a number of portals
then everything whose distance from a portal is (x, y) has to have the same color
case 1: there are two portals offset by (x, y)
they must have the same color
everything 1 below them must have the same color too


there is a 1 at (x, y). what's the nearest y2 so that there's another 1 at (x, y2)?
to obtain another 1, you can either travel +-(dx1, dy1) or +-(dx2, dy2)
let's say you add in the x & subtract in the y & dy1 & dy2 have the same sign
consider lcm(dx1, dx2) which is dx1 * dx2 / gcd(dx1, dx2)
the answer is (lcm/dx1) * dy1 - (lcm/dx2) * dy2
*/

long long abv(long long x) {
  return (long long) max(x, -x);
}

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  vector<array<int, 2>> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i][0] >> a[i][1];
  }
  if (n <= 2) {
    cout << -1 << '\n';
  } else if (n == 3) {
    sort(a.begin(), a.end());
    long long dif1 = a[1][0] - a[0][0], dif2 = a[2][0] - a[1][0],
      dif3 = a[1][1] - a[0][1], dif4 = a[2][1] - a[1][1];
    pv(dif1); pv(dif2); pv(dif3); pv(dif4);
    if ((dif1 == dif2 && dif3 == dif4) || (dif1 == 0 && dif2 == 0) || (dif3 == 0 && dif4 == 0)
      || (dif3 != 0 && abs(dif1) > abs(dif3) && dif1 % dif3 == 0 && dif4 * (dif1 / dif3) == dif2)
      || (dif1 != 0 && abs(dif3) > abs(dif1) && dif3 % dif1 == 0 && dif2 * (dif3 / dif1) == dif4)) {
      cout << -1 << '\n';
    } else {
      long long g = (dif1 == 0 ? dif2 : (dif2 == 0 ? dif1 : gcd(dif1, dif2)));
      long long h = (dif1 == 0 ? abs(dif3) : (dif2 == 0 ? abs(dif4)
        : (dif3 == 0 ? abs(dif4) : (dif4 == 0 ? abs(dif3) : -1))));
      if (h == -1) {
        long long lcm = (long long) dif1 * dif2 / g; pv(lcm);
        h = abv(lcm / dif1 * dif3 - lcm / dif2 * dif4);
      }
      pv(g); pv(h);
      cout << g * h << '\n';
    }
  }
}

• Subtask 1: 1 / 1
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35