제출 #1131047

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131047		huutuan	IOI 바이러스 (JOI21_fever)	C++20	6 / 100	3 ms	4288 KiB

fever

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct Point{
   int x, y;
   Point (int _x=0, int _y=0){
      x=_x, y=_y;
   }
   Point operator+(Point &a){ return Point(x+a.x, y+a.y); }
   Point operator-(Point &a){ return Point(x-a.x, y-a.y); }
   Point operator*(int d){ return Point(x*d, y*d); }
};

const int N=1e5+10;
int n;
Point a[N], b[N];
int f[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i) cin >> a[i].x >> a[i].y;
   // for (int i=1; i<=n; ++i) cout << (a[i]-a[1]).x << ' ' << (a[i]-a[1]).y << '\n';
   for (int i=n; i>=1; --i) a[i]=(a[i]-a[1])*2;
   int ans=0;
   auto calc=[&](){
      for (int i=1; i<=n; ++i){
         if (a[i].y>=a[i].x && a[i].y<=-a[i].x) b[i]=Point(1, 0);
         else if (a[i].y<=-a[i].x) b[i]=Point(0, 1);
         else if (a[i].y>=a[i].x) b[i]=Point(0, -1);
         else b[i]=Point(-1, 0);
      }
      priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
      memset(f, 0x3f, sizeof f);
      f[1]=0;
      pq.emplace(0, 1);
      set<pair<int, int>> st1, st2, st3, st4;
      while (pq.size()){
         int i=pq.top().second, d=pq.top().first; pq.pop();
         if (f[i]!=d) continue;
         bool f1=0, f2=0, f3=0, f4=0;
         if (b[i].y) f1=st1.emplace(a[i].x, b[i].y==-1).second;
         if (b[i].x) f2=st2.emplace(a[i].y, b[i].x==-1).second;
         f3=st3.emplace(a[i].x-a[i].y, (b[i].y==-1 || b[i].x==-1)).second;
         f4=st4.emplace(a[i].x+a[i].y, (b[i].y==1 || b[i].x==-1)).second;
         for (int j=1; j<=n; ++j) if (i!=j){
            int t=(abs(a[i].x-a[j].x)+abs(a[i].y-a[j].y))/2;
            if (t<d || f[j]<=t) continue;
            bool check=0;
            if (a[i].x==a[j].x){
               if (f1) check=(a[i].y<a[j].y && b[i].y==1 && b[j].y==-1) || (a[i].y>a[j].y && b[j].y==1 && b[i].y==-1);
            }else if (a[i].y==a[j].y){
               if (f2) check=(a[i].x<a[j].x && b[i].x==1 && b[j].x==-1) || (a[i].x>a[j].x && b[j].x==1 && b[i].x==-1);
            }else if (a[i].x-a[i].y==a[j].x-a[j].y){
               if (f3) check=(a[i].x<a[j].x && ((b[i].x==1 && b[j].y==-1) || (b[i].y==1 && b[j].x==-1))) || (a[i].x>a[j].x && ((b[j].x==1 && b[i].y==-1) || (b[j].y==1 && b[i].x==-1)));
            }else if (a[i].x+a[i].y==a[j].x+a[j].y){
               if (f4) check=(a[i].x<a[j].x && ((b[i].x==1 && b[j].y==1) || (b[i].y==-1 && b[j].x==-1))) || (a[i].x>a[j].x && ((b[j].x==1 && b[i].y==1) || (b[j].y==-1 && b[i].x==-1)));
            }
            if (check){
               f[j]=t;
               pq.emplace(t, j);
            }
         }
      }
      // for (int i=1; i<=n; ++i) if (f[i]<1e18) cout << i << ' ';
      // cout << '\n';
      ans=max(ans, accumulate(f+1, f+n+1, 0ll, [&](int x, int y){ return x+(y<1e18); }));
   };
   auto rotate=[&](){
      for (int i=1; i<=n; ++i) a[i]=Point(-a[i].y, a[i].x);
   };
   for (int i=1; i<=4; ++i){
      calc();
      rotate();
   }
   cout << ans << '\n';
   return 0;
}

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