본문 바로가기

코딩/문제풀이

Problem Solving Diary #2

IOI 2015 Day 1. Teams

서브태스크 1, 2 (34점)

$O(NQ)$로 풀 수 있는 경우 어떻게 쉽게 풀 수 있을까요? 그리디한 접근을 생각해 봅시다. 정원 수가 작은 프로젝트부터 보면, 현재 넣을 수 있는 사람들 중 $B_i$가 가장 작은 사람을 넣는 게 이득입니다. (나중에 가능성이 있는 사람을 남겨 둬야 하므로) 따라서 사람들을 $A_i$ 순서로 정렬하고 프로젝트를 정원 수에 따라 정렬한 뒤에, 힙을 사용하여 $B_i$가 작은 사람부터 뽑아내면 됩니다. 시간 복잡도는 $O(NQ \log N)$입니다.

 

더보기
#include <bits/stdc++.h>
#include "teams.h"

using namespace std;

typedef long long ll;

int n;
pair<int, int> arr[500002];

void init(int N, int A[], int B[]){
    n = N;
    for(int i=1; i<=n; i++) arr[i] = make_pair(A[i-1], B[i-1]);
    sort(arr+1, arr+n+1);
}

priority_queue<int, vector<int>, greater<int> > pq;

int can(int M, int K[]){
    while(!pq.empty()) pq.pop();
	sort(K, K+M);
    int pnt = 1;
	for(int i=0; i<M; i++){
	    while(pnt <= n && arr[pnt].first <= K[i]){
            pq.push(arr[pnt++].second);
	    }
	    int cnt = 0;
	    while(!pq.empty() && cnt<K[i]){
            if(pq.top() < K[i]){
                pq.pop();
                continue;
            }
            pq.pop();
            cnt++;
	    }
	    if(cnt < K[i]) return false;
    }
    return true;
}

 

서브태스크 3, 4 (100점)

위 풀이를 $O(S log^2 N)$으로 줄이는 것은 크게 어렵지 않습니다.

 

각 학생별로 $(A_i, B_i)$에 점을 찍으면 위 그림과 같이 나오는데, 여기서 34점 그리디 풀이는 $y=x$ 직선 위의 점 하나에서 시작하는 직사각형 영역을 잡고, 아직 고르지 않은 점 중 가장 아래쪽에 있는 점들을 고르는 것과 같습니다.

 

이 작업을 계속 반복하면, 고른 점들의 영역이 아래와 같이 오른쪽으로 갈수록 $y$가 단조감소하는 꼴이 됩니다.

저 영역을 스택으로 관리하고, 고르지 않은 영역 중 어디까지 골라야 하는지를 머지 소트 트리 위에서 이분 탐색을 하는 것으로 구현하면 $O(N \log N + Q \log^2 N)$에 문제를 풀 수 있습니다.

 

더보기
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll D = 1000000000;

struct segTree{
    vector<ll> tree[2000002];

    void init(int i, int l, int r){
        if(l==r){
            sort(tree[i].begin(), tree[i].end());
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m);
        init(i*2+1, m+1, r);
        tree[i].resize((int)tree[i*2].size() + (int)tree[i*2+1].size());
        merge(tree[i*2].begin(), tree[i*2].end(), tree[i*2+1].begin(), tree[i*2+1].end(), tree[i].begin());
    }

    void addPoint(int i, int l, int r, int x, ll y){
        if(l==r){
            tree[i].push_back(y);
            return;
        }
        int m = (l+r)>>1;
        if(x <= m) addPoint(i*2, l, m, x, y);
        else addPoint(i*2+1, m+1, r, x, y);
    }

    int query(int i, int l, int r, int s, int e, ll vl, ll vr){
        if(r<s || e<l) return 0;
        if(s<=l && r<=e){
            return upper_bound(tree[i].begin(), tree[i].end(), vr) - lower_bound(tree[i].begin(), tree[i].end(), vl);
        }
        int m = (l+r)>>1;
        return query(i*2, l, m, s, e, vl, vr) + query(i*2+1, m+1, r, s, e, vl, vr);
    }

    pair<int, int> findLim(int i, int l, int r, int x, ll s, ll e, int &lim){
        if(l==r){
            int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
            if(tret <= lim){
                lim -= tret;
                return make_pair(-1, -1);
            }
            return make_pair(l-1, lim);
        }
        int m = (l+r)>>1;
        if(x>m) return findLim(i*2+1, m+1, r, x, s, e, lim);

        if(x <= l){
            int tret = upper_bound(tree[i].begin(), tree[i].end(), e) - lower_bound(tree[i].begin(), tree[i].end(), s);
            if(tret <= lim){
                lim -= tret;
                return make_pair(-1, -1);
            }
        }

        auto tmp = findLim(i*2, l, m, x, s, e, lim);
        if(tmp.first >= 0) return tmp;
        return findLim(i*2+1, m+1, r, x, s, e, lim);
    }
} tree;
vector<ll> occ[500002];

int n;
pair<ll, int> p[500002];

void init(int N, int A[], int B[]){
    n = N;
    for(int i=0; i<n; i++){
        p[i] = make_pair(D*A[i] + i, B[i]);
        occ[p[i].second].push_back(p[i].first);
        tree.addPoint(1, 1, n, p[i].second, p[i].first);
    }
    tree.init(1, 1, n);

    for(int i=1; i<=n; i++) sort(occ[i].begin(), occ[i].end());
}

int k;
int arr[200002];
stack<pair<ll, int> > stk;

int can(int M, int K[]){
    k = M;
    for(int i=1; i<=k; i++) arr[i] = K[i-1];
    sort(arr+1, arr+k+1);

    while(!stk.empty()) stk.pop();
    stk.push(make_pair(0, n));

    for(int i=1; i<=k; i++){
        int x = arr[i], lim = arr[i];
        while(i<k && arr[i] == arr[i+1]){
            i++;
            x += arr[i];
            if(x>n) return false;
        }

        while(!stk.empty() && stk.top().second < arr[i]) stk.pop();

        while(!stk.empty()){
            pair<ll, int> tmp = stk.top();
            int ret = tree.query(1, 1, n, lim, tmp.second, tmp.first+1, D*arr[i]+(D-1));
            if(ret > x) break;
            stk.pop();
            x -= ret;
            lim = tmp.second+1;
        }

        if(stk.empty()){
            if(x) return false;
            stk.push(make_pair(D*arr[i]+(D-1), n));
            continue;
        }

        pair<ll, int> p = stk.top();
        pair<int, int> tmp = tree.findLim(1, 1, n, lim, p.first+1, D*arr[i]+(D-1), x);
        int bx = tmp.first;

        if(x){
            auto it = lower_bound(occ[bx+1].begin(), occ[bx+1].end(), p.first+1) + (x-1);
            if(stk.top().second == bx+1) stk.pop();
            stk.push(make_pair(*it, bx+1));
        }
        if(stk.top().second == bx) stk.pop();
        stk.push(make_pair(D*arr[i]+(D-1), bx));
    }

    return true;
}

int main() {
    int N;
    scanf("%d", &N);
    int *A = (int*)malloc(sizeof(int)*(unsigned int)N);
    int *B = (int*)malloc(sizeof(int)*(unsigned int)N);
    for (int i = 0; i < N; ++i) {
    	scanf("%d %d", &A[i], &B[i]);
    }
    init(N, A, B);
    int Q;
    scanf("%d", &Q);
    for (int i = 0; i < Q; ++i) {
    	int M;
    	scanf("%d", &M);
        int *K = (int*)malloc(sizeof(int)*(unsigned int)M);
    	for (int j = 0; j < M; ++j) {
    		scanf("%d", &K[j]);
    	}
    	printf("%d\n", can(M, K));
    }
    return 0;
}

 

IOI 2015 Day 1. Scales

6개의 추를 주어진 4가지 연산으로 정렬하는 문제입니다. 우선 $Q$를 알아내 봅시다. 항상 9번의 쿼리를 이용하는 풀이를 제출하면 45.45점을 받습니다. 따라서 $Q=6$임을 얻을 수 있습니다. $6! \le 3^6$이긴 한데, 차이가 사실상 없다시피 하기 때문에 쪼개는 게 쉽지 않아 보입니다. 따라서 그냥 아무 생각 없이 나이브를 돌려도 decision tree를 1초 내로 만들 수 있습니다. decision tree를 만들면 사실상 문제가 해결됩니다. 

 

IOI 2018 Day 1. Werewolf

답이 항상 같은 트리를 구축할 수 있을 거라고 생각하고 열심히 고민해 봤는데, 정해가 상당히 다른 방향이라는 것을 알고 좌절했습니다. 스스로 풀이를 생각하는 데 실패했기 때문에 풀이는 따로 적지 않겠습니다.

 

더보기
#include <bits/stdc++.h>
#include "werewolf.h"

using namespace std;

typedef long long ll;

struct unionFind{
    int par[400002], root[400002], idx[400002];
    vector<int> child[400002];
    int l[400002], r[400002], inCnt = 0;
    int sps[400002][20];
    int n;

    void init(int _n, int dfidx){
        n = _n - 1;
        for(int i=0; i<=n; i++) par[i] = root[i] = i, idx[i] = dfidx;
    }

    int find(int x){
        if(x==root[x]) return x;
        return root[x] = find(root[x]);
    }

    void merge(int x, int y, int z){
        int newNode = ++n;
        x = find(x), y = find(y);
        par[x] = root[x] = par[y] = root[y] = newNode;
        child[newNode].push_back(x);
        child[newNode].push_back(y);
        par[newNode] = root[newNode] = newNode;
        idx[newNode] = z;
    }

    void ss(int x){
        if(child[x].empty()){
            l[x] = r[x] = inCnt++;
            return;
        }
        l[x] = INT_MAX;
        for(auto y: child[x]){
            ss(y);
            l[x] = min(l[x], l[y]);
            r[x] = max(r[x], r[y]);
        }
    }

    void makeDB(){
        n++;
        par[n-1] = par[n] = n;
        for(int i=0; i<=n; i++) sps[i][0] = par[i];
        for(int d=1; d<20; d++) for(int i=0; i<=n; i++) sps[i][d] = sps[sps[i][d-1]][d-1];
    }
} t1, t2;

struct segTree{
    vector<int> tree[800002];
    void init(int i, int l, int r, int *A){
        if(l==r){
            tree[i].push_back(A[l]);
            return;
        }
        int m = (l+r)>>1;
        init(i*2, l, m, A);
        init(i*2+1, m+1, r, A);
        tree[i].resize(tree[i*2].size() + tree[i*2+1].size());
        merge(tree[i*2].begin(), tree[i*2].end(), tree[i*2+1].begin(), tree[i*2+1].end(), tree[i].begin());
    }

    bool chk(int i, int l, int r, int s, int e, int s1, int e1){
        if(r<s || e<l) return false;
        if(s<=l && r<=e) return upper_bound(tree[i].begin(), tree[i].end(), e1) != lower_bound(tree[i].begin(), tree[i].end(), s1);
        int m = (l+r)>>1;
        return chk(i*2, l, m, s, e, s1, e1) || chk(i*2+1, m+1, r, s, e, s1, e1);
    }
} tree;

int n, m, q;
vector<bool> vec;
vector<int> link[200002];
int arr[200002];
vector<int> ans;

vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
    n = N;
    m = (int)X.size();
    q = S.size();
    for(int i=0; i<m; i++) link[X[i]].push_back(Y[i]), link[Y[i]].push_back(X[i]);

    t1.init(n, n);
    t2.init(n, -1);
    for(int i=n-1; i>=0; i--){
        for(auto y: link[i]){
            if(y<i) continue;
            if(t1.find(i) != t1.find(y)) t1.merge(i, y, i);
        }
    }
    for(int i=0; i<n; i++){
        for(auto y: link[i]){
            if(y>i) continue;
            if(t2.find(i) != t2.find(y)) t2.merge(i, y, i);
        }
    }

    t1.ss(t1.n);
    t2.ss(t2.n);
    for(int i=0; i<n; i++) arr[t1.l[i]] = t2.l[i];
    tree.init(1, 0, n-1, arr);

    t1.makeDB();
    t2.makeDB();

    for(int i=0; i<q; i++){
        int s = S[i], e = E[i], l = L[i], r = R[i];
        int x1 = s, x2 = e;

        for(int d=19; d>=0; d--){
            if(t1.sps[x1][d] == 0 || t1.sps[x1][d] == t1.n) continue;
            if(t1.idx[t1.sps[x1][d]] < l) continue;
            x1 = t1.sps[x1][d];
        }
        for(int d=19; d>=0; d--){
            if(t2.sps[x2][d] == 0 || t2.sps[x2][d] == t2.n) continue;
            if(t2.idx[t2.sps[x2][d]] > r) continue;
            x2 = t2.sps[x2][d];
        }

        ans.push_back(tree.chk(1, 0, n-1, t1.l[x1], t1.r[x1], t2.l[x2], t2.r[x2]));
    }
    return ans;
}

 

IOI 2016 Day 2. Aliens

Alien's trick 기초 연습문제입니다. $O(N^2K)$ 시간에 풀 수 있는 2차원 DP 점화식을 어렵지 않게 얻어낼 수 있고, CHT와 Alien's trick을 사용해 최적화할 수 있습니다. 개인적으로 Alien's trick에서 발생하는 코너 케이스가 정말 까다로웠던 문제인 것 같습니다. (또 Alien's Trick이라는 고정관념을 가지고 생각하다 보니 CHT가 생각만큼 잘 안 떠오르기도 했습니다.)

 

검색해 본 결과 반정수점에서 이분탐색을 하는 등의 기법을 사용하면 쉽게 처리가 된다고 하는 것 같은데, 이 부분에 대해서는 더 공부해 봐야 할 것 같습니다.

 

더보기
#include <bits/stdc++.h>
#include "aliens.h"

using namespace std;

typedef long long ll;

int n, m, k;
ll x[500002], y[500002];

void makeArr(vector<int>&, vector<int>&);
pair<ll, int> calc(ll);

ll take_photos(int N, int M, int K, vector<int> r, vector<int> c){
    m = M, k = K;
    makeArr(r, c);
    k = min(n, k);

    assert(calc(0).second == n);
    assert(calc(1e12*2+1).second == 1);

    ll L = 0, R = 1e12, ans = 1e12;
    while(L <= R){
        ll M = (L+R)>>1;
        if(calc(M).second <= k) ans = M, R = M-1;
        else L = M+1;
    }

    auto p = calc(ans);
    if(p.second == k) return p.first - ans * (k-1);

    auto p1 = calc(ans);
    auto p2 = calc(ans-1);
    assert(p1.second <= k && p2.second > k);
    int x1 = p1.second, x2 = p2.second;
    ll y1 = p1.first, y2 = p2.first;
    ll d1 = y1 - (x1-1) * ans, d2 = y2 - (x2-1) * (ans-1);
    return d2 + (d1 - d2) / (x2 - x1) * (x2 - k);
}

void makeArr(vector<int> &r, vector<int> &c){
    vector<pair<int, int> > vec;
    int N = (int)r.size();
    for(int i=0; i<N; i++){
        if(r[i] > c[i]) swap(r[i], c[i]);
        vec.push_back(make_pair(r[i], c[i]));
    }
    sort(vec.begin(), vec.end(), [&](pair<int, int> &x, pair<int, int> &y){
        return x.second < y.second;
    });

    vector<pair<int, int> > stk;
    for(int i=0; i<N; i++){
        if(!stk.empty() && stk.back().second == vec[i].second && stk.back().first <= vec[i].first) continue;
        while(!stk.empty() && stk.back().first >= vec[i].first) stk.pop_back();
        stk.push_back(vec[i]);
    }

    n = (int)stk.size();
    for(int i=1; i<=n; i++) x[i] = stk[i-1].first, y[i] = stk[i-1].second;

    for(int i=1; i<n; i++){
        assert(x[i] < x[i+1]);
        assert(y[i] < y[i+1]);
    }
}

ll quot(ll a, ll b){
    if(a>=0) return a/b;
    return a/b - !!(a%b);
}

struct Line{
    ll a, b; ll start; int cnt;
    Line(ll a, ll b, int cnt): a(a), b(b), cnt(cnt){}
    Line(ll a, ll b, ll start, int cnt): a(a), b(b), start(start), cnt(cnt){}

    ll val(ll x){
        return a*x+b;
    }

    ll cross(const Line &r)const{
        ll A = r.a - a;
        ll B = r.b - b;
        assert(A >= 0);
        return quot(-B+A-1, A);
    }
};

ll DP[500002];
int cnt[500002];
vector<Line> vec;
int pnt = 0;

pair<ll, int> calc(ll lambda){
    for(int i=1; i<=n; i++){
        DP[i] = (y[i] - x[1] + 1) * (y[i] - x[1] + 1);
        cnt[i] = 1;
    }
    pnt = 0;
    vec.clear();
    vec.push_back(Line(2, 3e12, -1e18, 0));

    for(int i=1; i<=n; i++){
        while(pnt >= (int)vec.size() || vec[pnt].start > y[i]) --pnt;
        while(pnt+1 < (int)vec.size() && y[i] >= vec[pnt+1].start) ++pnt;

        ll val = vec[pnt].val(y[i]) + y[i]*y[i] + lambda;
        if(DP[i] > val){
            DP[i] = val;
            cnt[i] = vec[pnt].cnt + 1;
        }

        if(i==n) break;
        Line tmp = Line(-(x[i+1]-1) * 2, (x[i+1]-1) * y[i] * 2 - y[i] * y[i] + DP[i], cnt[i]);
        if(x[i+1] > y[i]) tmp = Line(-(x[i+1]-1) * 2, (x[i+1]-1)*(x[i+1]-1) + DP[i], cnt[i]);

        while((int)vec.size() >= 2 && vec.back().start > tmp.cross(vec[(int)vec.size()-1])){
            vec.pop_back();
            if((int)vec.size() == pnt) pnt--;
        }
        tmp.start = tmp.cross(vec.back());
        vec.push_back(tmp);
    }

    return make_pair(DP[n], cnt[n]);
}

 

IOI 2019 Day 2. Broken Lines

가장 기본적인 형태로 아래와 같은 세 가지 형태는 쉽게 처리가 가능합니다.

  • 점들이 오른쪽 위로만 진행하는 단조증가형 형태 (Type 1)
  • 나선 형태로 선분을 그어 처리할 수 있는 형태 (Type 2)
  • 점들이 오른쪽 위로 짝수 번 이동하고, 오른쪽 아래로 짝수 번 이동하고, ... 를 반복하는 형태 (Type 3)

사실 Type 3은 쓸모가 없습니다. $N$개의 점을 모두 Type 2로 처리할 수 있다면 좋겠지만, 그럴 수 없는 경우가 생깁니다. 바로 어떤 점이 다른 모든 점보다 왼쪽 위에 있거나, 오른쪽 위에 있거나, ... 한 형태입니다. 따라서 두 개의 Type 1 형태를 만든다고 생각하고(/ 방향과 반대 방향), 가장 오른쪽 위에 있거나 왼쪽 아래에 있는 점은 / 방향 Type 1 목록에 넣어줄 수 있습니다. 마찬가지로 가장 왼쪽 위나 오른쪽 아래에 있는 점도 처리가 가능합니다.

 

이러한 점이 없는 경우 상하좌우 네 점은 Type 2 형태로 처리가 가능합니다. 따라서 Type 2를 먼저 처리해 준 뒤, 양 대각선 방향의 Type 1 형태를 각각 처리해 주면 됩니다. Type 2를 바깥쪽부터 처리해도 되긴 하는데, 어차피 안에서부터 나와야 해서 그냥 처음부터 안쪽에서 시작하면 구현이 간단해집니다.

 

코드...인데, 코너 케이스 처리를 일부 안 해서 항상 동작하진 않습니다. 주어진 데이터에 대해서는 모두 동작하는 것으로 보입니다.

 

더보기
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int LIM = 2000000000;

struct Point{
    int x, y, idx;
    Point(){}
    Point(int x, int y, int idx): x(x), y(y), idx(idx){}

    bool operator<(const Point &r)const{
        return x<r.x;
    }
};

int n;
int x[100002], y[100002];

priority_queue<Point> pqL, pqR, pqU, pqD;
bool chk[100002];

vector<int> loop, zig1, zig2; /// O, /, \.
vector<pair<int, int> > ans;

int main(){
//    freopen("tests/08.in", "r", stdin);
//    freopen("tests/08.out", "w", stdout);
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &x[i], &y[i]);
        pqL.push(Point(-x[i], y[i], i));
        pqR.push(Point(x[i], y[i], i));
        pqD.push(Point(-y[i], x[i], i));
        pqU.push(Point(y[i], x[i], i));
    }

    char turn = 'U';
    int px=0, py=0;

    while(true){
        while(1){
            while(!pqL.empty() && chk[pqL.top().idx]) pqL.pop();
            while(!pqR.empty() && chk[pqR.top().idx]) pqR.pop();
            while(!pqD.empty() && chk[pqD.top().idx]) pqD.pop();
            while(!pqU.empty() && chk[pqU.top().idx]) pqU.pop();
            if(!pqR.empty() && pqR.top().idx == pqU.top().idx){
                int k = pqR.top().idx;
                chk[k] = 1;
                zig1.push_back(k);
                continue;
            }
            if(!pqR.empty() && pqR.top().idx == pqD.top().idx){
                int k = pqR.top().idx;
                chk[k] = 1;
                zig2.push_back(k);
                continue;
            }
            if(!pqL.empty() && pqL.top().idx == pqD.top().idx){
                int k = pqL.top().idx;
                chk[k] = 1;
                zig1.push_back(k);
                continue;
            }
            if(!pqL.empty() && pqL.top().idx == pqU.top().idx){
                int k = pqL.top().idx;
                chk[k] = 1;
                zig2.push_back(k);
                continue;
            }
            break;
        }

        if(pqL.empty()){
            assert(pqR.empty());
            assert(pqD.empty());
            assert(pqU.empty());
            break;
        }

        chk[pqL.top().idx] = 1;
        loop.push_back(pqL.top().idx);

        chk[pqD.top().idx] = 1;
        loop.push_back(pqD.top().idx);

        chk[pqR.top().idx] = 1;
        loop.push_back(pqR.top().idx);

        chk[pqU.top().idx] = 1;
        loop.push_back(pqU.top().idx);
    }

    reverse(loop.begin(), loop.end());
    for(int d=0; d<(int)loop.size()/4; d++){
        int i = d*4;
        py = y[loop[i]];
        ans.push_back(make_pair(px, py));

        if(x[loop[i]] > px){ /// 오른쪽으로 돌아야 함
            px = x[loop[i+1]];
            ans.push_back(make_pair(px, py));

            py = y[loop[i+2]];
            ans.push_back(make_pair(px, py));

            px = x[loop[i+3]];
            ans.push_back(make_pair(px, py));

//            if((i+4)>=(int)loop.size()) ans.push_back(make_pair(x[loop[i+3]], y[loop[i+3]]));
        }
        else{
            px = x[loop[i+3]];
            ans.push_back(make_pair(px, py));

            py = y[loop[i+2]];
            ans.push_back(make_pair(px, py));

            px = x[loop[i+1]];
            ans.push_back(make_pair(px, py));
//            if((i+4)>=(int)loop.size()) ans.push_back(make_pair(x[loop[i+1]], y[loop[i+1]]));
        }
    }

    assert(!zig1.empty());
    assert(!zig2.empty());
    sort(zig1.begin(), zig1.end(), [&](int a, int b){
        return x[a] < x[b];
    });
    sort(zig2.begin(), zig2.end(), [&](int a, int b){
        return x[a] < x[b];
    });

    for(int i=0; i<(int)zig1.size()-1; i++){
        assert(y[zig1[i]] < y[zig1[i+1]]);
    }
    for(int i=0; i<(int)zig2.size()-1; i++){
        assert(y[zig2[i]] > y[zig2[i+1]]);
    }
    for(auto x: zig1) chk[x] = 1;
    for(auto x: zig2) chk[x] = 1;
    for(int i=1; i<=n; i++){
        if(!chk[i]){
            return 1;
        }
    }

    if(turn == 'U'){
        ans.push_back(make_pair(px, LIM));
        px = x[zig1.back()], py = LIM;
        turn = 'D';
        ans.push_back(make_pair(px, py));

        for(int i=(int)zig1.size()-2; i>=0; i--){
            if(turn == 'D'){
                py = y[zig1[i]];
                ans.push_back(make_pair(px, py));
                turn = 'L';
            }
            else{
                px = x[zig1[i]];
                ans.push_back(make_pair(px, py));
                turn = 'D';
            }
        }
    }
    else if(turn == 'D'){
        ans.push_back(make_pair(px, -LIM));
        px = x[zig1.front()], py = -LIM;
        turn = 'U';
        ans.push_back(make_pair(px, py));

        for(int i=1; i<(int)zig1.size(); i++){
            if(turn == 'U'){
                py = y[zig1[i]];
                ans.push_back(make_pair(px, py));
                turn = 'R';
            }
            else{
                px = x[zig1[i]];
                ans.push_back(make_pair(px, py));
                turn = 'U';
            }
        }
    }
    else if(turn == 'L'){
        ans.push_back(make_pair(-LIM, py));
        px = -LIM, py = y[zig1.front()];
        turn = 'R';
        ans.push_back(make_pair(px, py));

        for(int i=1; i<(int)zig1.size(); i++){
            if(turn == 'U'){
                py = y[zig1[i]];
                ans.push_back(make_pair(px, py));
                turn = 'R';
            }
            else{
                px = x[zig1[i]];
                ans.push_back(make_pair(px, py));
                turn = 'U';
            }
        }
    }
    else{ /// 'R'
        ans.push_back(make_pair(LIM, py));
        px = LIM, py = y[zig1.back()];
        turn = 'L';
        ans.push_back(make_pair(px, py));

        for(int i=(int)zig1.size()-2; i>=0; i--){
            if(turn == 'D'){
                py = y[zig1[i]];
                ans.push_back(make_pair(px, py));
                turn = 'L';
            }
            else{
                px = x[zig1[i]];
                ans.push_back(make_pair(px, py));
                turn = 'D';
            }
        }
    }




    if(turn == 'U'){
        ans.push_back(make_pair(px, LIM));
        px = x[zig2.front()], py = LIM;
        turn = 'D';
        ans.push_back(make_pair(px, py));

        for(int i=1; i<(int)zig2.size(); i++){
            if(turn == 'D'){
                py = y[zig2[i]];
                ans.push_back(make_pair(px, py));
                turn = 'R';
            }
            else{
                px = x[zig2[i]];
                ans.push_back(make_pair(px, py));
                turn = 'D';
            }
        }
        ans.push_back(make_pair(x[zig2.back()], y[zig2.back()]));
    }
    else if(turn == 'D'){
        ans.push_back(make_pair(px, -LIM));
        px = x[zig2.back()], py = -LIM;
        turn = 'U';
        ans.push_back(make_pair(px, py));

        for(int i=(int)zig2.size()-2; i>=0; i--){
            if(turn == 'U'){
                py = y[zig2[i]];
                ans.push_back(make_pair(px, py));
                turn = 'L';
            }
            else{
                px = x[zig2[i]];
                ans.push_back(make_pair(px, py));
                turn = 'U';
            }
        }
        ans.push_back(make_pair(x[zig2.front()], y[zig2.front()]));
    }
    else if(turn == 'L'){
        ans.push_back(make_pair(-LIM, py));
        px = -LIM, py = y[zig2.front()];
        turn = 'R';
        ans.push_back(make_pair(px, py));

        for(int i=1; i<(int)zig2.size(); i++){
            if(turn == 'D'){
                py = y[zig2[i]];
                ans.push_back(make_pair(px, py));
                turn = 'R';
            }
            else{
                px = x[zig2[i]];
                ans.push_back(make_pair(px, py));
                turn = 'D';
            }
        }
        ans.push_back(make_pair(x[zig2.back()], y[zig2.back()]));
    }
    else{ /// 'R'
        ans.push_back(make_pair(LIM, py));
        px = LIM, py = y[zig2.back()];
        turn = 'L';
        ans.push_back(make_pair(px, py));

        for(int i=(int)zig2.size()-2; i>=0; i--){
            if(turn == 'U'){
                py = y[zig2[i]];
                ans.push_back(make_pair(px, py));
                turn = 'L';
            }
            else{
                px = x[zig2[i]];
                ans.push_back(make_pair(px, py));
                turn = 'U';
            }
        }
        ans.push_back(make_pair(x[zig2.front()], y[zig2.front()]));
    }

    printf("%d\n", (int)ans.size());
    for(auto p: ans) printf("%d %d\n", p.first, p.second);
}

 

'코딩 > 문제풀이' 카테고리의 다른 글

BOJ 7469 K번째 수 (in Q log N!)  (3) 2021.08.21
Problem Solving Diary #2  (0) 2021.06.15
Problem Solving Diary #1  (0) 2021.06.11

태그