제출 #1131052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131052		huutuan	IOI 바이러스 (JOI21_fever)	C++20	11 / 100	3 ms	4168 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); }
   bool operator<(Point &a){ return tie(x, y)<tie(a.x, a.y); }
   bool operator!=(Point &a){ return tie(x, y)!=tie(a.x, a.y); }
};

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);
      // map<int, vector<int>> m1, m2, m3, m4;
      // for (int i=1; i<=n; ++i){
      //    m1[a[i].x].push_back(i);
      //    m2[a[i].y].push_back(i);
      //    m3[a[i].x-a[i].y].push_back(i);
      //    m4[a[i].x+a[i].y].push_back(i);
      // }
      // for (auto &i:m1){
      //    sort(i.second.begin(), i.second.end(), [&](int x, int y){
      //       return a[x].y<a[y].y;
      //    });
      // }
      // for (auto &i:m2){
      //    sort(i.second.begin(), i.second.end(), [&](int x, int y){
      //       return a[x].x<a[y].x;
      //    });
      // }
      // for (auto &i:m3){
      //    sort(i.second.begin(), i.second.end(), [&](int x, int y){
      //       return a[x].x<a[y].x;
      //    });
      // }
      // for (auto &i:m4){
      //    sort(i.second.begin(), i.second.end(), [&](int x, int y){
      //       return a[x].x<a[y].x;
      //    });
      // }
      map<pair<int, int>, pair<int, int>> mt1, mt2, mt3, mt4;
      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;
         pair<int, int> i1(a[i].x, b[i].y==-1), i2(a[i].y, b[i].x==-1), i3(a[i].x-a[i].y, (b[i].y==-1 || b[i].x==-1)), i4(a[i].x+a[i].y, (b[i].y==1 || b[i].x==-1));
         int t1=abs(a[i].y), t2=abs(a[i].x), t3=abs(a[i].x-(a[i].x-a[i].y)/2), t4=abs(a[i].x-(a[i].x+a[i].y)/2);
         if (b[i].y) f1=mt1[i1].second==t1;
         if (b[i].x) f2=mt2[i2].second==t2;
         f3=mt3[i3].second==t3;
         f4=mt4[i4].second==t4;
         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;
               pair<int, int> i1(a[j].x, b[j].y==-1), i2(a[j].y, b[j].x==-1), i3(a[j].x-a[j].y, (b[j].y==-1 || b[j].x==-1)), i4(a[j].x+a[j].y, (b[j].y==1 || b[j].x==-1));
               int t1=abs(a[j].y), t2=abs(a[j].x), t3=abs(a[j].x-(a[j].x-a[j].y)/2), t4=abs(a[j].x-(a[j].x+a[j].y)/2);
               if (b[j].y) mt1.insert({i1, {(int)1e18, (int)1e18}}), mt1[i1]=min(mt1[i1], {t, t1});
               if (b[j].x) mt2.insert({i2, {(int)1e18, (int)1e18}}), mt2[i2]=min(mt2[i2], {t, t2});
               mt3.insert({i3, {(int)1e18, (int)1e18}}), mt3[i3]=min(mt3[i3], {t, t3});
               mt4.insert({i4, {(int)1e18, (int)1e18}}), mt4[i4]=min(mt4[i4], {t, t4});
               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: 5 / 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