제출 #389891

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
389891		doowey	IOI Fever (JOI21_fever)	C++14	37 / 100	5046 ms	2544 KiB

fever

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 100;
ll Y[N], X[N];    // [y;x]
int dir[4][2] = {{0,+1},{0,-1},{+1,0},{-1,0}};

int n;

int go[N];

ll low[N];
bool pro[N];

int solve(){
    go[0] = 0;
    for(int i = 2; i <= n; i ++ ){
        if(abs(Y[i]) == abs(X[i])){
            if(X[i] > 0){
                if(Y[i] > 0){
                    go[i] = 3;
                }
                else{
                    go[i] = 2;
                }
            }
            else{
                go[i] = 0;
            }
        }
        else{
            if(abs(Y[i]) > abs(X[i])){
                if(Y[i] > 0){
                    go[i] = 3;
                }
                else{
                    go[i] = 2;
                }
            }
            else{
                if(X[i] < 0){
                    go[i] = 0;
                }
                else{
                    go[i] = 1;
                }
            }
        }
    }
    for(int i = 1; i <= n; i ++ ){
        low[i] = (ll)1e18;
        pro[i]=false;
    }
    low[1]=0;
    int id = -1;
    int sol = 0;
    ll AY, AX;
    ll tt;
    for(int i = 1; i <= n; i ++ ){
        id = -1;
        for(int j = 1; j <= n; j ++ ){
            if(pro[j] || low[j] == (ll)1e18) continue;
            if(id == -1 || low[j] < low[id]){
                id = j;
            }
        }
        if(id == -1) continue;
        pro[id] = true;
        sol ++ ;
        for(int j = 1; j <= n; j ++ ){
            if(pro[j]) continue;
            if(go[id] == go[j]) continue;
            AY = dir[go[id]][0] - dir[go[j]][0];
            AX = dir[go[id]][1] - dir[go[j]][1];
            if(AY * (X[j] - X[id]) == AX * (Y[j] - Y[id])){
                if(AY != 0){
                    tt = (Y[j] - Y[id]) / AY;
                }
                else{
                    tt = (X[j] - X[id]) / AX;
                }
                if(tt >= low[id]){
                    low[j] = min(low[j], tt);
                }
            }
        }
    }
    return sol;
}

int main(){
    fastIO;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> Y[i] >> X[i];
        Y[i] *= 2ll;
        X[i] *= 2ll;
        if(i > 1) {
            Y[i] -= Y[1];
            X[i] -= X[1];
        }
    }
    Y[1] = 0;
    X[1] = 0;
    int sol = solve();
    for(int i = 1; i <= n; i ++ ){
        X[i] = -X[i];
    }
    sol = max(sol, solve());
    for(int i = 1; i <= n; i ++ ){
        swap(X[i], Y[i]);
    }
    sol = max(sol, solve());
    for(int i = 1; i <= n; i ++ ){
        X[i] = -X[i];
    }
    sol = max(sol, solve());
    cout << sol << "\n";
    return 0;
}

• 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