Submission #1031114

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031114		AdamGS	IOI Fever (JOI21_fever)	C++17	37 / 100	5076 ms	49648 KiB

fever

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(ll a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e5+7;
pair<ll,ll>T[LIM];
ll odl[LIM], kier[LIM], n;
int solve() {
  rep(i, n) odl[i]=INF;
  kier[0]=0;
  for(int i=1; i<n; ++i) {
    int a=abs(T[0].st-T[i].st), b=abs(T[0].nd-T[i].nd);
    if(b>a) {
      if(T[0].nd<T[i].nd) kier[i]=1;
      else kier[i]=3;
    } else if(b<a) {
      if(T[0].st<T[i].st) kier[i]=2;
      else kier[i]=0;
    } else if(T[i].st<T[0].st) kier[i]=0;
    else if(T[0].nd<T[i].nd) kier[i]=1;
    else kier[i]=3;
  }
  priority_queue<pair<ll,ll>>q;
  q.push({0, 0});
  int ans=0;
  while(!q.empty()) {
    ll o=-q.top().st, p=q.top().nd; q.pop();
    if(odl[p]<=o) continue;
    odl[p]=o;
    ++ans;
    rep(i, n) if(odl[i]==INF) {
      rep(j, 4) {
        kier[i]=(kier[i]+1)%4;
        kier[p]=(kier[p]+1)%4;
        T[i]={T[i].nd, -T[i].st};
        T[p]={T[p].nd, -T[p].st};
        if(kier[p]==0) {
          if(kier[i]==1) {
            if(T[p].st-T[p].nd==T[i].st-T[i].nd && T[p].st+odl[p]<=T[i].st) {
              q.push({T[p].st-T[i].st, i});
              continue;
            }
          }
          if(kier[i]==3) {
            if(T[p].st+T[p].nd==T[i].st+T[i].nd && T[p].st+odl[p]<=T[i].st) {
              q.push({T[p].st-T[i].st, i});
              continue;
            }
          }
          if(kier[i]==2) {
            if(T[p].nd==T[i].nd && T[p].st+odl[p]<=T[i].st-odl[p]) {
              q.push({-(T[i].st-T[p].st)/2, i});
              continue;
            }
          }
        }
      }
    }
  }
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> n;
  rep(i, n) cin >> T[i].st >> T[i].nd;
  rep(i, n) T[i]={2*T[i].st, 2*T[i].nd};
  int ans=0;
  rep(i, 4) {
    ans=max(ans, solve());
    rep(j, n) T[j]={-T[j].nd, T[j].st};
  }
  cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31