Submission #701934

#TimeUsernameProblemLanguageResultExecution timeMemory
701934Jarif_RahmanIOI Fever (JOI21_fever)C++17
25 / 100
5069 ms7032 KiB
#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 == 1 && a < x) mn = abs(a-x), d = 3;
                if(b == y && abs(a-x) < mn && abs(a-x) >= t && dd == 3 && a > x) mn = abs(a-x), d = 1;
                if(a == x && abs(b-y) < mn && abs(b-y) >= t && dd == 0 && b < y) mn = abs(b-y), d = 2;
                if(a == x && abs(b-y) < mn && abs(b-y) >= t && dd == 2 && b > y) mn = abs(b-y), d = 0;  
            }
            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";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...