oj.uz

답안 #711277

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
711277 2023-03-16T12:55:29 Z Username4132 Izvanzemaljci (COI21_izvanzemaljci) C++14
38 / 100
 172 ms 9808 KB 
#include<cassert>
#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; assert(l<=r && d<=u);
    }
    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];
ll 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){
    if(m<=0) return rect();
    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=rect();
    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){
            ll 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[i+1]+height));
        }
    }
    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))){
            ll 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[0].x + height));
        }
    }
    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-(ll)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){
            ll 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()+(ll)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();
}

Compilation message

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 280 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 46 ms 9592 KB Output is correct
8 Correct 47 ms 9696 KB Output is correct
9 Correct 42 ms 9680 KB Output is correct
10 Correct 43 ms 9676 KB Output is correct
11 Correct 43 ms 9652 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 124 ms 9684 KB Output is correct
11 Correct 131 ms 9692 KB Output is correct
12 Correct 124 ms 9808 KB Output is correct
13 Correct 147 ms 9684 KB Output is correct
14 Correct 128 ms 9684 KB Output is correct
15 Correct 127 ms 9700 KB Output is correct
16 Correct 94 ms 9568 KB Output is correct
17 Correct 120 ms 8912 KB Output is correct
18 Correct 92 ms 8628 KB Output is correct
19 Correct 128 ms 7888 KB Output is correct
20 Correct 92 ms 8404 KB Output is correct
21 Correct 172 ms 9760 KB Output is correct
22 Correct 138 ms 9672 KB Output is correct
23 Correct 145 ms 9692 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 1 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 468 KB Output is correct
2 Incorrect 4 ms 468 KB Integer -2392564465 violates the range [1, 2*10^9]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Incorrect 4 ms 468 KB Integer -2376787775 violates the range [1, 2*10^9]
4 Halted 0 ms 0 KB -