Submission #545432

#	Time	Username	Problem	Language	Result	Execution time	Memory
545432		Dan13llljws	IOI Fever (JOI21_fever)	C++14	25 / 100	428 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], vis[MM], d[4][MM];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
int solve(int i, int di, int j, int dj){
    // (x[i], y[i]) + t(dx[di], dy[di]) == (x[j], y[j]) + t(dx[dj], dy[dj]);
    // x[i] + t(dx[di]) == x[j] + t(dx[dj])
    // y[i] + t[dy[di]) == y[j] + t(dy[dj])
    // (x[i] - x[j]) / (dx[dj] - dx[di]) = t
    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 {
        if ((x[i] - x[j]) % (dx[dj] - dx[di]) || (y[i] - y[j]) % (dy[dj] - dy[di])) return -1;
        int t = (x[i] - x[j]) / (dx[dj] - dx[di]), s = (y[i] - y[j]) / (dy[dj] - dy[di]);
//         cout << t<< ' '<< s << endl;
        return t == s ? t : -1;
    }
}
int main(){
    n = re;
    for (int i = 1; i <= n; i++) x[i] = re, y[i] = re;
//     cout<< solve(6, 1, 10, 3);
    for (int d1 = 0; d1 < 4; d1++){
        memset(d, 0x3f, sizeof d), memset(vis, 0, sizeof vis);
        int cur = 0; d[d1][1] = 0;
        for (int i = 1; i <= n; i++){
            int u = -1, dir, mint = 1e9;
            for (int j = 1; j <= n; j++)
                for (int di = 0; di < 4; di++)
                    if (!vis[j] && d[di][j] < mint) mint = d[di][j], u = j, dir = di;
            if (u == -1) break;
            vis[u] = 1, cur++;
//             cout << u << ' ' << mint << ' ' << dir << endl;
            for (int v = 1; v <= n; v++)
                if (!vis[v])
                    for (int di = 0; di < 4; di++){
                        if (di == dir) continue;
//                         cout << v <<' ' << di << endl;
                        int t = solve(u, dir, v, di);
//                         cout << t << endl;
                        if (t >= 0 && t >= mint) d[di][v] = min(d[di][v], t);
                    }
        } ans = max(ans, cur);
    } printf("%d\n", ans);
}

• 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