Submission #1135382

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135382		pudelos	Park (BOI16_park)	C++20	100 / 100	169 ms	6472 KiB

park

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define gc getchar_unlocked
#define sz(A) (int)(A.size())
#define ll long long
#define eb emplace_back
#define pb push_back
#define pi pair<int, int>
#define f first
#define s second
#define rs resize
#define V vector

const int inf=1e18;
basic_string<int> sciana = {0, 0, 0, 0};

int n, m, w, h;
V<pair<int, pi>> drzewo, pytania;
V<basic_string<bool>> czy;
V<basic_string<int>> dp;
basic_string<bool> vis;
bool found;

inline bool odlK(int a, int b, int r) {
  ll da = (drzewo[a].s.f-drzewo[b].s.f);
  ll db = (drzewo[a].s.s-drzewo[b].s.s);
  ll odl = 2*r + drzewo[a].f + drzewo[b].f;
  return (odl*odl > da*da + db*db);
}

inline bool odl(int v, int b, int r) {
  if(b%2==0) return (abs(sciana[b]-drzewo[v].s.s) < 2*r+drzewo[v].f);
  return (abs(sciana[b]-drzewo[v].s.f) < 2*r+drzewo[v].f);
}

void wcz(int &a) {
  a=0;
  char c=gc();
  while(c<'0'||c>'9') c=gc();
  while(c>='0'&&c<='9') a=10*a+(int)(c-'0'), c=gc();
}

void dfs(int v, int r, int b) {
  if(found) return;
  vis[v]=1;
  if(odl(v, b, r)) {
    found=1;
    return;
  }
  FOR(i, 1, n) {
    if(vis[i]) continue;
    if(!odlK(v, i, r)) continue;
    dfs(i, r, b);
    if(found) return;
  }
}

signed main() {
  // cin.tie(0) -> ios_base::sync_with_stdio(0);
  // cin >> n >> m >> w >> h;
  wcz(n); wcz(m); wcz(w); wcz(h);

  sciana = {0, w, h, 0};
  dp.rs(4);
  FOR(i, 0, 3) dp[i].rs(4);

  drzewo.rs(n+1);
  vis.rs(n+1);
  pytania.rs(m+1);
  czy.rs(m+1);
  int x, y, r;
  FOR(i, 1, n) {
    // cin >> x >> y >> r;
    wcz(x); wcz(y); wcz(r);
    drzewo[i] = {r, {x, y}};
  }
  int e;
  FOR(i, 1, m) {
    // cin >> r >> e;
    wcz(r); wcz(e);
    --e;
    pytania[i] = {r, {i, e}};
    czy[i].rs(4);
  }
  sort(pytania.begin()+1, pytania.end());

  FOR(a, 0, 3) FOR(b, a+1, 3) {
    int lo = 0;
    int hi = m;
    while(lo<hi) {
      int mid = (lo+hi+1)/2;
      int r = pytania[mid].f;
      found=0;
      FOR(i, 1, n) vis[i]=0;
      FOR(i, 1, n) {
        if(found) break;
        if(vis[i]) continue;
        if(odl(i, a, r)) {
          dfs(i, r, b);
        }
      }
      if(found) hi=mid-1;
      else lo=mid;
    }
    if(lo==0) dp[a][b]=dp[b][a]=-1;
    dp[a][b]=dp[b][a]=pytania[lo].f;
  }

  FOR(i, 1, m) {
    auto p = pytania[i];
    int e = p.s.s;
    int idx = p.s.f;
    int r = p.f;
    FOR(xb, 0, 3) {
      if(abs(xb-e)==0) {
        czy[idx][xb]=1;
        continue;
      } else if(abs(xb-e)%2==1) {
        czy[idx][xb]=1;
        int s=min(xb,e);
        if(min(xb,e)==0 && max(xb,e)==3) s=3;
        for(int b=(s+1)%4; b!=s; b=(b+1)%4) if(r>dp[s][b]) czy[idx][xb]=0;
      } else if(abs(xb-e)%2==0) {
        czy[idx][xb]=1;
        int s=min(xb,e);
        for(int a=s; a!=(s+2)%4; a=(a+1)%4)
          for(int b=(s+2)%4; b!=(s)%4; b=(b+1)%4)
            if(r>dp[a][b]) czy[idx][xb]=0;
      }
    }
  }

  FOR(i, 1, m) {
    string odp = "";
    FOR(j, 0, 3) {
      if(czy[i][j]) {
        int out = j+1;
        odp=odp+to_string(out);
      }
    }
    cout << odp << '\n';
  }
}

• Subtask 1: 27 / 27
• Subtask 2: 31 / 31
• Subtask 3: 42 / 42