Submission #1236528

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236528		theSkeleton	IOI Fever (JOI21_fever)	C++20	19 / 100	1112 ms	589824 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 = 3e3+5;

typedef long double ld;

pll arr[mx];
int dir[mx];
pii sav[5]{
    MP(0,0),
    MP(-1,0),
    MP(0,-1),
    MP(1,0),
    MP(0,1),
};
ld 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]==0){
                sp.PB(i);
            }
        }
    }
    int o=1;
    heap<pair<ld,int>> 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+mx,inf);
        lst.push(MP(0,1));
        while(!lst.empty()){
            int i=lst.top().S;
            ld di=lst.top().F;
            dp[i]=min(dp[i],di);
            lst.pop();
            for(int j=1;j<=n;j++){
                if(i!=j){
                    if(dir[i]%2==dir[j]%2){
                        ld v0,v1,d0,d1;
                        if(dir[i]%2){
                            v0=arr[i].F;
                            v1=arr[j].F;
                            d0=arr[i].S;
                            d1=arr[j].S;
                        }
                        else{
                            v0=arr[i].S;
                            v1=arr[j].S;
                            d0=arr[i].F;
                            d1=arr[j].F;
                        }
                        if(d0==d1){
                            if((v0<v1&&dir[i]>dir[j])||(v0>v1&&dir[i]<dir[j])){
                                ld t=((v0+v1)/(ld)2)-min(v0,v1);
                                if(di<t){
                                    lst.push(MP(t,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.push(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);
    }
    cout<<o;
    return 0;
}

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