Submission #701933

#	Time	Username	Problem	Language	Result	Execution time	Memory
701933		Jarif_Rahman	IOI Fever (JOI21_fever)	C++17	25 / 100	5079 ms	7064 KiB

fever

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

int test(vector<pair<int, int>> v, int D){
    int cnt = 1;

    vector<tuple<int, int, int, int>> ill = {{v[0].f, v[0].sc, 0, D}};
    v.erase(v.begin());

    while(!ill.empty()){
        vector<pair<int, int>> _v;
        vector<tuple<int, int, int, int>> _ill;
        swap(_v, v);
        for(auto [x, y]: _v){
            int mn = 2e9, d = -1;
            for(auto [a, b, t, dd]: ill){
                if((a+b == x+y || a-b == x-y) && 2*abs(a-x) < mn && 2*abs(a-x) >= t){
                    if(dd == 0 && y < b) continue;
                    if(dd == 1 && x < a) continue;
                    if(dd == 2 && y > b) continue;
                    if(dd == 3 && x > a) continue;

                    mn = 2*abs(a-x);
                    if(dd == 0 || dd == 2) d = x < a ? 1:3;
                    if(dd == 1 || dd == 3) d = y < b ? 0:2;
                }
                if(b == y && abs(a-x) < mn && abs(a-x) >= t && dd%2 == 1) mn = abs(a-x), d = 2-dd;
                if(a == x && abs(b-y) < mn && abs(b-y) >= t && dd%2 == 0) mn = abs(b-y), d = 4-dd;
            }
            if(d != -1) _ill.pb({x, y, mn, d}), cnt++;
            else v.pb({x, y});
        }
        swap(ill, _ill);
    }

    return cnt;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n; cin >> n;
    vector<pair<int, int>> v(n);
    for(auto &[x, y]: v) cin >> x >> y;

    cout << max(max(test(v, 0), test(v, 1)), max(test(v, 2), test(v, 3))) << "\n";
}

• 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