Submission #1236486

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236486		theSkeleton	IOI Fever (JOI21_fever)	C++20	25 / 100	5095 ms	9668 KiB

fever

//!!in the name of god!!
#include<bits/stdc++.h>
#define space <<' '<<
#define endl '\n'
#define inf 1e18
#define F first
#define S second
#define PB push_back
#define PF push_front
#define pll pair<ll,ll>
#define pii pair<int,int>
#define md(a) ((a+mod)%mod)
#define MP(a,b) make_pair(a,b)
#define all(a) a.begin(),a.end()
#define MT(a,b,c) make_tuple(a,b,c)
#define has(a,b) (a.find(b)!=a.end())
typedef long long ll;
using namespace std;
template<typename t> using heap=
priority_queue<t,vector<t>,greater<t>>;
const int mx = 2e5+5;

pll arr[mx];
int dir[mx];
pii sav[5]{
    MP(0,0),
    MP(-1,0),
    MP(0,-1),
    MP(1,0),
    MP(0,1),
};
ll dp[mx];

inline int fix(int i,ll x,ll y){
    int o=0;
    if(abs(x-arr[i].F)>abs(y-arr[i].S)){
        o=(x>arr[i].F)?3:1;
    }
    if(abs(x-arr[i].F)<abs(y-arr[i].S)){
        o=(y>arr[i].S)?4:2;
    }
    return o;
}

int main(){
    std::ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    vector<int> sp;
    for(ll x,y,i=1;i<=n;i++){
        cin>>x>>y;
        arr[i]=MP(x,y);
        if(1<i){
            dir[i]=fix(i,arr[1].F,arr[1].S);
            if(!dir[i]){
                sp.PB(i);
            }
        }
    }
    int o=1;
    set<pll> lst;
    for(int d=1;d<=4;d++){
        dir[1]=d;
        ll x=arr[1].F+sav[d].F;
        ll y=arr[1].S+sav[d].S;
        for(int i:sp){
            dir[i]=fix(i,x,y);
        }
        fill(dp,dp+n+1,inf);
        lst.insert(MP(0,1));
        while(!lst.empty()){
            int i=lst.begin()->S;
            ll di=lst.begin()->F;
            dp[i]=di;
            lst.erase(lst.begin());
            for(int j=1;j<=n;j++){
                if(i!=j){
                    if(dir[i]%2==dir[j]%2){
                        if(dir[i]!=dir[j]){
                            bool check=((dir[i]%2)?arr[i].S==arr[j].S:arr[i].F==arr[j].F);
                            ll v0=dir[i]%2?arr[i].F:arr[i].S;
                            ll v1=dir[j]%2?arr[j].F:arr[j].S;
                            check&=di<=(abs(v0-v1)/2);
                            check&=dp[j]>(abs(v0-v1)/2);
                            if(check){
                                lst.insert(MP(abs(v0-v1)/2,j));
                            }
                        }
                    }
                    else{
                        int t=fix(i,arr[j].F,arr[j].S);
                        if(t==0){
                            bool xk=arr[j].F<arr[i].F?(dir[i]==1||dir[j]==3):(dir[i]==3||dir[j]==1);
                            bool yk=arr[j].S<arr[i].S?(dir[i]==2||dir[j]==4):(dir[i]==4||dir[j]==2);
                            if(xk&&yk){
                                if(di<abs(arr[i].F-arr[j].F)){
                                    lst.insert(MP(abs(arr[i].F-arr[j].F),j));
                                }
                            }
                        }
                    }
                }
            }
        }
        int c=0;
        for(int i=1;i<=n;i++){
            c+=dp[i]<inf;
        }
        o=max(o,c);
        for(int i:sp){
            dir[i]=0;
        }
    }
    cout<<o;
    return 0;
}

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