Submission #905230

#	Time	Username	Problem	Language	Result	Execution time	Memory
905230		alexander707070	IOI Fever (JOI21_fever)	C++14	37 / 100	3692 ms	524288 KiB

fever

#include<bits/stdc++.h>
#define MAXN 500007
using namespace std;

struct point{
    int x,y,pos;
    /// 0-up 1-right 2-down 3-left
};

struct collision{
    int from,to,tim;

    inline friend bool operator < (collision fr,collision sc){
        return fr.tim<sc.tim;
    }
};

int n,cnt,ans;
point p[MAXN];
vector<collision> w;
bool inf[MAXN];

int quadrant(point p){
    if(p.x>=0 and p.y>=0)return 0;
    if(p.x<0 and p.y>=0)return 1;
    if(p.x<0 and p.y<0)return 2;
    return 3;
}

void orientate_points(){
    for(int f=2;f<=n;f++){
        if(quadrant(p[f])==0){
            if(p[f].x>p[f].y)p[f].pos=3;
            if(p[f].x<p[f].y)p[f].pos=2;
            if(p[f].x==p[f].y){
                if(p[1].pos==1 or p[1].pos==2)p[f].pos=2;
                else p[f].pos=3;
            }
        }

        if(quadrant(p[f])==1){
            if(-p[f].x>p[f].y)p[f].pos=1;
            if(-p[f].x<p[f].y)p[f].pos=2;
            if(-p[f].x==p[f].y){
                if(p[1].pos==0 or p[1].pos==1)p[f].pos=1;
                else p[f].pos=2;
            }
        }

        if(quadrant(p[f])==2){
            if(-p[f].x>-p[f].y)p[f].pos=1;
            if(-p[f].x<-p[f].y)p[f].pos=0;
            if(-p[f].x==-p[f].y){
                if(p[1].pos==2 or p[1].pos==1)p[f].pos=1;
                else p[f].pos=0;
            }
        }

        if(quadrant(p[f])==3){
            if(p[f].x>-p[f].y)p[f].pos=3;
            if(p[f].x<-p[f].y)p[f].pos=0;
            if(p[f].x==-p[f].y){
                if(p[1].pos==2 or p[1].pos==3)p[f].pos=3;
                else p[f].pos=0;
            }
        }
    }
}

int collide(point a,point b){
    int s=( abs(a.x-b.x)+abs(a.y-b.y) )/2;
    
    if(a.pos==0)a.y+=s;
    if(a.pos==1)a.x+=s;
    if(a.pos==2)a.y-=s;
    if(a.pos==3)a.x-=s;

    if(b.pos==0)b.y
    +=s;
    if(b.pos==1)b.x+=s;
    if(b.pos==2)b.y-=s;
    if(b.pos==3)b.x-=s;

    if(a.x==b.x and a.y==b.y)return s;
    return -1;
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
    }
    
    for(int i=2;i<=n;i++){
        p[i].x-=p[1].x;
        p[i].y-=p[1].y;

        p[i].x*=2; p[i].y*=2;
    }
    p[1].x=p[1].y=0;

    for(int i=0;i<4;i++){
        p[1].pos=i;

        orientate_points();
        for(int f=1;f<=n;f++)inf[f]=false;
        inf[1]=true;

        w.clear(); cnt=0;

        for(int f=1;f<=n;f++){
            for(int k=f+1;k<=n;k++){
                w.push_back({f,k,collide(p[f],p[k])});
            }
        }
        sort(w.begin(),w.end());

        for(int f=0;f<w.size();f++){
            if(w[f].tim==-1)continue;
            if(inf[w[f].from])inf[w[f].to]=true;
            if(inf[w[f].to])inf[w[f].from]=true;
        }

        for(int f=1;f<=n;f++){
            if(inf[f])cnt++;
        }

        ans=max(ans,cnt);
    }

    cout<<ans<<"\n";
 
    return 0;
}

Compilation message (stderr)

fever.cpp: In function 'int main()':
fever.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<collision>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int f=0;f<w.size();f++){
      |                     ~^~~~~~~~~

• 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