제출 #710844

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
710844		Username4132	Izvanzemaljci (COI21_izvanzemaljci)	C++14	38 / 100	79 ms	10300 KiB

izvanzemaljci

#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)

struct pt{
    int x, y, ind;
    pt(int X, int Y, int I){
        x=X, y=Y, ind=I;
    }
    pt(){}
};

struct rect{
    int assi;
    ll l, d, r, u;
    rect(ll L, ll D, ll R, ll U, int A=2000000000){
        l=L, d=D, r=R, u=U, assi=A;
    }
    rect(){l=d=r=u=0, assi=-1;}
    void transform(bool a, bool b, bool c){
        int aux;
        if(a) aux=l, l=-r, r=-aux;
        if(b) aux=d, d=-u, u=-aux;
        if(c) swap(l, d), swap(r, u);
    }
};

struct sol{
    bool valid;
    rect re[3];
    sol(){
        valid = false;
    }
    sol(rect R1, rect R2, rect R3){
        re[0]=R1, re[1]=R2, re[2]=R3, valid=true;
    }
    void print(){forn(i, 3) if(re[i].assi!=-1) printf("%lld %lld %lld", re[i].l, re[i].d, re[i].u-re[i].d), printf("\n");}
    void dummySquare(int num){
        int start = 2001000000;
        forn(i, 3){
            num+=(re[i].assi==-1);
            if(re[i].assi==-1 && num>3) re[i]=rect(start, 0, start+1, 1, 0), start+=2;
        }
    }
    void transform(bool a, bool b, bool c){
        forn(i, 3) re[i].transform(a, b, c);
    }
};

const int MAXN=100010, INF=2000000100;
int n, k, ext[MAXN], calc[MAXN], st[2*MAXN], st1[MAXN], st2[MAXN];
bool seen[MAXN];
pt srt[2][2][2][MAXN], varg[MAXN];
rect le[2][2][2], oneans;

auto fstCmp = [](pt a, pt b){
    return a.x<b.x;
};

auto sndCmp = [](pt a, pt b){
    return a.y<b.y;
};

rect cover(pt* arr, int m){
    int mn=INF, mx=-INF;
    forn(i, m) mn=min(mn, arr[i].y), mx=max(mx, arr[i].y);
    return rect(arr[0].x, mn, arr[m-1].x, mx);
}

rect push_corner(rect re, int dir, int len){
    switch(dir){
        case 0: return rect(re.l, re.d, re.l+len, re.d+len);
        case 1: return rect(re.r-len, re.d, re.r, re.d+len);
        case 2: return rect(re.l, re.u-len, re.l+len, re.u);
        case 3: return rect(re.r-len, re.u-len, re.r, re.u);
    }
}

rect rightmost(pt* arr, int m, int side){
    int mn=INF, mx=-INF; rect ret;
    forn(i, m){
        mx=max(mx, arr[i].y), mn=min(mn, arr[i].y);
        if(arr[i].x-arr[0].x>side || mx-mn>side) break;
        if(i==m-1 || arr[i+1].x!=arr[i].x) ret = rect(arr[0].x, mn, arr[i].x, mx, i);
    }
    return ret;
}

sol low_high_check(pt* arr, int l, int r, int side){

    int high_left = max_element(arr, arr+l, sndCmp)->y;
    int high_center = max_element(arr+l, arr+r, sndCmp)->y;
    int low_center = min_element(arr+l, arr+r, sndCmp)->y;
    int low_right = min_element(arr+r, arr+n, sndCmp)->y;
    if(high_left>high_center || low_center>low_right) return sol();

    ext[l]=low_center, ext[r-1]=high_center;
    dforn(i, l) ext[i]=min(ext[i+1], arr[i].y);
    forsn(i, r, n) ext[i]=max(ext[i-1], arr[i].y);
    dforn(i, l) calc[i]=ext[i+1]-arr[i].x;
    forsn(i, r, n) calc[i]=ext[i-1]-arr[i].x;
    dforn(i, l-1) calc[i]=max(calc[i+1], calc[i]);
    forsn(i, r+1, n) calc[i]=min(calc[i-1], calc[i]);

    int pos=r;
    forn(i, l){
        while(pos<n && (calc[pos]+2>calc[i] || (ext[pos-1]==ext[i+1] && arr[pos].x-arr[i].x==2))) ++pos;
        int width = arr[pos].x - arr[i].x - 2, height = max(ext[pos-1]-ext[i+1], 1);
        if(height<=width && height<=side){
            int left_edge = max(arr[i].x+1, arr[r-1].x-height);
            int szl = lower_bound(arr, arr+n, pt(left_edge, -INF, 0), fstCmp)-arr;
            int szr = upper_bound(arr, arr+n, pt(left_edge+height, INF, 0), fstCmp)-arr;

            return sol(push_corner(cover(arr, szl), 1, side),
            push_corner(cover(arr+szr, n-szr), 0, side),
            rect(left_edge, ext[i+1], left_edge+height, ext[pos-1]));
        }
    }
    return sol();
}

sol lowest_check(pt* arr, pt* brr, int l, int r, int side){
    if(arr[r-1].x - arr[l].x > side) return sol();
    int pos = find_if(arr, arr+n, [&brr](pt a){
        return a.ind==brr[0].ind;
    }) - arr;
    if(pos<l || pos>=r) return sol();
    int L=pos, R=pos;
    forn(i, n) seen[i]=false;
    forn(i, n){
        seen[brr[i].ind]=true;
        while(L>0 && seen[arr[L-1].ind]) --L;
        while(R<n-1 && seen[arr[R+1].ind]) ++R;
        int height=max(brr[i].x-brr[0].x, 1);

        if(L<=l && R>=r-1 && height<=side && (L==0 || R==n-1 || (height<=arr[R+1].x-arr[L-1].x-2))){
            int left_edge = max(L==0? -INF : arr[L-1].x+1, arr[r-1].x-height);
            int szl = lower_bound(arr, arr+n, pt(left_edge, -INF, 0), fstCmp)-arr;
            int szr = upper_bound(arr, arr+n, pt(left_edge+height, INF, 0), fstCmp)-arr;

            return sol(push_corner(cover(arr, szl), 1, side),
            push_corner(cover(arr+szr, n-szr), 0, side),
            rect(left_edge, brr[0].x, left_edge+height, brr[i].x));
        }
    }
    return sol();
}

sol equal_check(pt* arr, int l, int r, int side){

    int L=0, R=0;
    deque<int> mn, mx;
    forn(i, n) st1[i]=arr[i].x+1, st2[i]=arr[i].x-side;
    merge(st1, st1+n, st2, st2+n, st);
    mn.push_back(arr[0].y);
    mx.push_back(arr[0].y);
    forn(i, 2*n){
        while(R<n && arr[R+1].x<=st[i]+side){
            ++R;
            while(!mn.empty() && mn.back()>arr[R].y) mn.pop_back();
            while(!mx.empty() && mx.back()<arr[R].y) mx.pop_back();
            mx.push_back(arr[R].y);
            mn.push_back(arr[R].y);
        }
        while(L<n && arr[L].x<st[i]){
            if(!mn.empty() && arr[L].y==mn.front()) mn.pop_front();
            if(!mx.empty() && arr[L].y==mx.front()) mx.pop_front();
            ++L;
        }
        if(L<=l && R>=r-1 && mx.front()-mn.front()<=side){
            int left_edge = max(arr[L-1].x+1, arr[r-1].x-side);

            return sol(push_corner(cover(arr, L), 1, side),
            push_corner(cover(arr+R+1, n-R-1), 0, side),
            rect(left_edge, mn.front(), left_edge+side, mn.front()+side));
        }
    }
    return sol();
}

sol check_two(pt* arr, int m, int side){
    rect fst=rightmost(arr, m, side);
    rect snd=rightmost(arr+fst.assi+1, m-fst.assi-1, side);
    if((fst.assi==-1 || snd.assi==-1) && fst.assi!=m-1 && snd.assi!=m-1) return sol();
    if(fst.assi+snd.assi+2==m) return sol(rect(), fst, snd);
    return sol();
}

sol v2_check(pt* arr, pt* brr, int side){
    int m=0;
    rect fst=rightmost(arr, n, side);
    forn(i, n) seen[i]=false;
    forn(i, fst.assi+1) seen[arr[i].ind]=true;
    forn(i, n) if(!seen[brr[i].ind]) varg[m++]=brr[i];
    sol ret = check_two(varg, m, side);
    if(m!=0 && !ret.valid) return sol();
    ret.transform(0, 0, 1);
    ret.re[0]=push_corner(fst, 1, side);
    ret.re[1]=push_corner(ret.re[1], 2, side);
    ret.re[2]=push_corner(ret.re[2], 0, side);

    return ret;
}

sol horizontal_checks(int side){
    
    forn(i, 2){
        sol ret = equal_check(srt[0][0][i], le[0][0][i].assi+1, n-le[1][0][i].assi-1, side);
        if(ret.valid){
            ret.transform(0, 0, i);
            return ret;
        }
    }

    forn(i, 2) forn(j, 2){
        sol ret = lowest_check(srt[0][i][j], srt[i][0][j^1], le[0][i][j].assi+1, n-le[1][i][j].assi-1, side);
        if(ret.valid){
            ret.transform(0, i, j);
            return ret;
        }

        ret = low_high_check(srt[0][i][j], le[0][i][j].assi+1, n-le[1][i][j].assi-1, side);
        if(ret.valid){
            ret.transform(0, i, j);
            return ret;
        }
    }

    return sol();
}

sol cross_checks(int side){
    forn(i, 2) forn(j, 2){
        sol ret = v2_check(srt[i][0][j], srt[0][i][j^1], side);
        if(ret.valid){
            ret.transform(i, 0, j);
            return ret;
        }
    }
    return sol();
}

sol test(int type, int side){
    if(side>=oneans.r-oneans.l) return sol(rect(), rect(), oneans);
    forn(i, 2) forn(j, 2) forn(w, 2) le[i][j][w] = rightmost(srt[i][j][w], n, side);

    forn(i, 2) if(le[0][0][i].assi+le[1][0][i].assi>=n-2){
        sol ret = check_two(srt[0][0][i], n, side);
        ret.re[1]=push_corner(ret.re[1], 1, side);
        ret.re[2]=push_corner(ret.re[2], 0, side);
        ret.transform(0, 0, i);
        return ret;
    }

    if(type==2) return sol();
    
    sol ret = horizontal_checks(side);
    if(ret.valid) return ret;

    ret = cross_checks(side);
    if(ret.valid) return ret;
    return sol();
}


int main(){
    scanf("%d %d", &n, &k);
    forn(i, n){
        int a, b; scanf("%d %d", &a, &b);
        srt[0][0][0][i] = pt(a, b, i);
        srt[0][0][1][i] = pt(b, a, i);
    }

    forn(i, 2) sort(srt[0][0][i], srt[0][0][i]+n, fstCmp);
    forn(i, 2) forn(j, n) srt[0][1][i][j]=pt(srt[0][0][i][j].x, -srt[0][0][i][j].y, srt[0][0][i][j].ind);
    forn(i, 2) forn(j, 2) forn(w, n) srt[1][i][j][w]=pt(-srt[0][i][j][n-1-w].x, srt[0][i][j][n-1-w].y, srt[0][i][j][n-1-w].ind);

    oneans = cover(srt[0][0][0], n);
    oneans = push_corner(oneans, 0, max(max(oneans.r-oneans.l, oneans.u-oneans.d), 1LL));
    if(k==1){
        sol(rect(), rect(), oneans).print();
        return 0;
    }

    int lo=0, hi=INF;
    sol ans;
    while(hi-lo>1){
        int mid = ((hi-lo)>>1)+lo;
        sol partial = test(k, mid);
        if(partial.valid) hi=mid, ans=partial;
        else lo=mid;
    }
    ans.dummySquare(k);
    ans.print();
}

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

izvanzemaljci.cpp: In function 'rect push_corner(rect, int, int)':
izvanzemaljci.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
   82 | }
      | ^
izvanzemaljci.cpp: In function 'int main()':
izvanzemaljci.cpp:272:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  272 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
izvanzemaljci.cpp:274:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  274 |         int a, b; scanf("%d %d", &a, &b);
      |                   ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 21 / 21
• Subtask 3: 12 / 12
• Subtask 4: 0 / 30
• Subtask 5: 0 / 32