제출 #701992

#제출 시각아이디문제언어결과실행 시간메모리
701992Jarif_RahmanIOI 바이러스 (JOI21_fever)C++17
25 / 100
5021 ms8208 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;
            int A = 0, B = 0;
            for(auto [a, b, t, dd]: ill){
                if((a+b == x+y || a-b == x-y) && abs(a-x) < mn && abs(a-x) >= t){
                    if(a < x) A++;
                    else B++;
                    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 = 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(min(A, B) > 0) exit(-1);
            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...