Submission #390265

#	Time	Username	Problem	Language	Result	Execution time	Memory
390265		doowey	IOI Fever (JOI21_fever)	C++14	37 / 100	5053 ms	27564 KiB

fever

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 100;
ll H[N], W[N];
int dir[4][2] = {{0,+1},{0,-1},{+1,0},{-1,0}};
int n;

int sol = 0;

struct E{
    ll val;
    ll sec;
    int idx;
    bool operator<(const E &e) const {
        if(val == e.val)
            return sec < e.sec;
        return val < e.val;
    }
};

vector<E> vv[4][4];
vector<ll> mx[4][4];
int go[N];
ll low[N];

int solve(){
    go[0] = 0;
    for(int i = 2; i <= n; i ++ ){
        if(abs(H[i]) == abs(W[i])){
            if(W[i] < 0) go[i] = 0;
            else {
                if(H[i] > 0)
                    go[i] = 3;
                else
                    go[i] = 2;
            }
        }
        else{
            if(abs(H[i]) > abs(W[i])){
                if(H[i] > 0)
                    go[i] = 3;
                else
                    go[i] = 2;
            }
            else{
                if(W[i] > 0){
                    go[i] = 1;
                }
                else{
                    go[i] = 0;
                }
            }
        }
        low[i]=(ll)1e18;
    }
    low[1]=0;
    for(int p = 0 ; p < 4; p ++ ){
        for(int q = 0; q < 4; q ++ ){
            vv[p][q].clear();
            mx[p][q].clear();
        }
    }
    E cur;
    ll AH, AW;
    for(int p = 0 ; p < 4; p ++ ){
        for(int i = 1; i <= n; i ++ ){
            if(go[i] != p){
                AH = dir[p][0] - dir[go[i]][0];
                AW = dir[p][1] - dir[go[i]][1];
                cur.val = AW * 1ll * H[i] - AH * 1ll * W[i];
                if(AH != 0) cur.sec = H[i] / AH;
                else cur.sec = W[i] / AW;
                cur.idx = i;
                vv[p][go[i]].push_back(cur);
                mx[p][go[i]].push_back(-(ll)1e18);
            }
        }
    }
    for(int p = 0 ; p < 4; p ++ ){
        for(int q = 0; q < 4; q ++ ){
            sort(vv[p][q].begin(), vv[p][q].end());
        }
    }
    int cnt = 0;
    int id = -1;
    ll nw;
    int cid;
    ll add;
    while(1){
        if(cnt == 0){
            id = 1;
            low[id] = 0;
        }
        else{
            nw = (ll)2e18;
            cid = -1;
            for(int p = 0;  p < 4; p ++ ){
                for(int q = 0; q < 4; q ++ ){
                    if(p == q) continue;
                    for(int j = 0 ;j < vv[p][q].size(); j ++ ){

                        if(vv[p][q][j].sec - mx[p][q][j] < nw){
                            nw = vv[p][q][j].sec - mx[p][q][j];
                            cid = vv[p][q][j].idx;
                        }

                    }
                }
            }
            if(nw > (ll)1e14) break;
            id = cid;
            low[id] = nw;
        }
        cnt ++ ;
        for(int p = 0 ; p < 4; p ++ ){
            if(p == go[id]) continue;
            for(int j = 0 ; j < vv[p][go[id]].size(); j ++ ){
                if(vv[p][go[id]][j].idx == id){
                    vv[p][go[id]][j].sec = (ll)1e18;
                }
            }
        }
        for(int nx = 0; nx < 4; nx ++ ){
            if(nx == go[id]) continue;
            AH = dir[go[id]][0] - dir[nx][0];
            AW = dir[go[id]][1] - dir[nx][1];
            cur.val = AW * H[id] - AH * W[id];
            cur.sec = low[id];
            if(AH != 0) add = H[id] / AH;
            else add = W[id] / AW;
            cur.sec += add;
            for(int i = 0 ; i < vv[go[id]][nx].size(); i ++ ){
                if(vv[go[id]][nx][i].val == cur.val && vv[go[id]][nx][i].sec >= cur.sec){
                    mx[go[id]][nx][i] = max(mx[go[id]][nx][i], add);
                }
            }
        }
    }
    return cnt;
}

int main(){
    fastIO;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> H[i] >> W[i];
        H[i] *= 2ll;
        W[i] *= 2ll;
        if(i > 1){
            H[i] -= H[1];
            W[i] -= W[1];
        }
    }
    H[1] = 0;
    W[1] = 0;
    int sol = solve();
    for(int i = 1; i <= n; i ++ ){
        W[i] = -W[i];
    }

    sol = max(sol, solve());
    for(int i = 1; i <= n; i ++ ){
        swap(H[i], W[i]);
    }
    sol = max(sol, solve());
    for(int i = 1; i <= n; i ++ ){
        W[i] = -W[i];
    }
    sol = max(sol, solve());
    cout << sol << "\n";
    return 0;
}

Compilation message (stderr)

fever.cpp: In function 'int solve()':
fever.cpp:111:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<E>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |                     for(int j = 0 ;j < vv[p][q].size(); j ++ ){
      |                                    ~~^~~~~~~~~~~~~~~~~
fever.cpp:128:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<E>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             for(int j = 0 ; j < vv[p][go[id]].size(); j ++ ){
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~
fever.cpp:143:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<E>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |             for(int i = 0 ; i < vv[go[id]][nx].size(); i ++ ){
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~

• 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