Submission #545530

#	Time	Username	Problem	Language	Result	Execution time	Memory
545530		Dan13llljws	IOI Fever (JOI21_fever)	C++14	37 / 100	281 ms	596 KiB

fever

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int read(){int s=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){s=(s<<3)+(s<<1)+ch-'0',ch=getchar();}return s*f;}
#define re read()
const int mod = 1e9 + 7, MM = 3005;
int n, ans, x[MM], y[MM], dir[MM], vis[MM], d[MM];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int solve(int i, int di, int j, int dj){
    if (dx[dj] == dx[di]){
        if (x[i] != x[j] || (y[i] - y[j]) % (dy[dj] - dy[di])) return -1;
        return (y[i] - y[j]) / (dy[dj] - dy[di]);
    } else if (dy[dj] == dy[di]){
        if (y[i] != y[j] || (x[i] - x[j]) % (dx[dj] - dx[di])) return -1;
        return (x[i] - x[j]) / (dx[dj] - dx[di]);
    } else {
        int t = (x[i] - x[j]) / (dx[dj] - dx[di]), s = (y[i] - y[j]) / (dy[dj] - dy[di]);
        return t == s ? t : -1;
    }
}
int main(){
    n = re;
    for (int i = 1; i <= n; i++) x[i] = re, y[i] = re;
    for (int i = 2; i <= n; i++) x[i] -= x[1], y[i] -= y[1], x[i] <<= 1, y[i] <<= 1;
    x[1] = y[1] = 0;
    for (int d1 = 0; d1 < 4; d1++){
        memset(d, 0x3f, sizeof d), memset(vis, 0, sizeof vis);
        for (int i = 1; i <= n; i++){
            if (abs(y[i]) < x[i]) dir[i] = 2;
            else if (abs(y[i]) <= -x[i]) dir[i] = 0;
            else if (abs(x[i]) <= y[i]) dir[i] = 3;
            else if (abs(x[i]) <= -y[i]) dir[i] = 1;
        } int cur = 0; d[1] = 0;
        for (int i = 1; i <= n; i++){
            int u = -1, mint = 0x3f3f3f3f;
            for (int j = 1; j <= n; j++)
                if (!vis[j] && d[j] < mint) mint = d[j], u = j;
            if (u == -1) break;
            vis[u] = 1, cur++;
            for (int v = 1; v <= n; v++)
                if (!vis[v]){
                    if (dir[v] == dir[u]) continue;
                    int t = solve(u, dir[u], v, dir[v]);
                    if (t >= mint) d[v] = min(d[v], t);
                }
        } ans = max(ans, cur);
        for (int i = 2; i <= n; i++){
            int tx = x[i], ty = -y[i];
            x[i] = ty, y[i] = tx;
        }
    } printf("%d\n", ans);
}

• 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