제출 #1209438

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1209438		Tyx2019	Road Construction (JOI21_road_construction)	C++20	32 / 100	10091 ms	59136 KiB

road_construction

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int mx = 2e9 + 5;
vector<pair<int, int>> V;
#define debug(x) if(0) cout << #x << " is " << x << endl;
int N, K;
vector<int> myfriends;
bool chk(int dist, bool walao = false){
    debug(walao)
    set<int> lolz;
    for(auto i:V){
        lolz.insert(i.first+dist);
        lolz.insert(i.first);
        lolz.insert(i.first+2*dist);
    }
    int cnt = 0;
    int cur = 0;
    int backcur = 0;
    int worstcur = 0;
    multiset<pair<int, int>> dudes;
    for(auto i:lolz){
        while(cur != V.size() && V[cur].first <= i){
            dudes.insert({V[cur].second, V[cur].first});
            if(V[cur].first == 2 && V[cur].second == 2){
                debug("hi")
            }
            cur++;
        }
        while(worstcur != V.size() && V[worstcur].first < i - 2 * dist){
            dudes.erase(dudes.find({V[worstcur].second, V[worstcur].first}));
            if(V[worstcur].first == 2 && V[worstcur].second == 2){
                debug("hi")
            }
            worstcur++;
        }
        while(backcur != V.size() && V[backcur].first == i - dist){
            int l = V[backcur].second - dist;
            int r = V[backcur].second + dist;
            auto it = dudes.lower_bound({l, -2*mx});
            while(it != dudes.end() && (*it).first <= r){
                int x1 = V[backcur].first;
                int y1 = V[backcur].second;
                int x2 = (*it).second;
                int y2 = (*it).first;
    
                assert(max(abs(x1-x2), abs(y1-y2)) <= dist);
                if(walao){
                    if(x1 == 2 && y1 == 0){
                        debug(x2)
                        debug(y2)
                        if(y2 == 0){
                            auto it2 = it;
                            it2++;
                            debug((*it2).first);
                            debug((*it2).second)
                        }
                    }
                    myfriends.push_back(max(abs(x1-x2), abs(y1-y2)));
                }
                it++;
                cnt++;
                if(cnt >= K) return true;
            }
            backcur++;
        }
    }
    debug(cnt)
    debug(dist)
    return false;
}
main(){
    cin >> N >> K;
    K = 2 * K + N;
    int X[N], Y[N];
    for(int i=0;i<N;i++) cin >> X[i] >> Y[i];
    for(int i=0;i<N;i++){
        if(X[i] - Y[i] == 2 && X[i]+Y[i] == 2) debug("hola")
        V.push_back({X[i] - Y[i], X[i] + Y[i]});
    }
    sort(V.begin(), V.end());
    int l = 0;
    int r = 1e10;
    while(r > l){
        int m = (l + r) >> 1;
        if(chk(m)) r = m;
        else l = m + 1;
    }
    chk(l-1, true);
    sort(myfriends.begin(), myfriends.end());
    for(int i=N;i<myfriends.size();i+=2) cout << myfriends[i] << "\n";
    int res = (K - myfriends.size()) / 2;
    for(int i=0;i<res;i++) cout << l << " " << '\n';
    debug(myfriends.size())

}

컴파일 시 표준 에러 (stderr) 메시지

road_construction.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main(){
      | ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 20
• Subtask 5: 27 / 27
• Subtask 6: 0 / 35