제출 #44073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
44073		Noam527	Pick (COI18_pick)	C++17	100 / 100	3 ms	860 KiB

pick

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;
 
void ab(vector<pair<int, int>> &p) {
    for (auto &i : p) swap(i.first, i.second);
}
void cd(vector<pair<int, int>> &p) {
    for (auto &i : p) i.second = -i.second;
}
pair<int, int> go(pair<int, int> &a, int p1, int p2) {
    return{ a.first + p1, a.second + p2 };
}
template<typename T>
int indexof(vector<T> &p, T val) {
    for (int i = 0; i < p.size(); i++)
        if (p[i] == val) return i;
    return -1;
}
 
template<typename T>
void combine(vector<T> &p, vector<T> &add, int afterind) {
    vector<T> tmp;
    while (afterind + 1 < p.size()) tmp.push_back(p.back()), p.pop_back();
    for (const auto &i : add) p.push_back(i);
    while (!tmp.empty()) p.push_back(tmp.back()), tmp.pop_back();
}
 
vector<pair<int, int>> ans;
 
void solvecase1(int a, int b, int c, int d) {
    if (a == 0 && c == 0) {
        if (b == 2) {
            ans.push_back({ 0, 0 });
            ans.push_back({ 0, 1 });
            for (int i = 0; i < d / 2; i++)
                ans.push_back(go(ans.back(), 1, -1));
            ans.push_back(go(ans.back(), 0, -1));
            for (int i = 1; i < d / 2; i++)
                ans.push_back(go(ans.back(), -1, 1));
        }
        else if (d == 2) {
            for (int i = 0; i <= b / 2; i++)
                ans.push_back({ 0, i });
            ans.push_back(go(ans.back(), 1, -1));
            for (int i = 0; i < b / 2; i++)
                ans.push_back(go(ans.back(), 0, -1));
        }
        else {
            for (int i = 0; i < b / 2; i++)
                ans.push_back({ 0, i });
            ans.push_back(go(ans.back(), 1, -1));
            for (int i = 0; i < b / 2; i++)
                ans.push_back(go(ans.back(), 0, -1));
            for (int i = 0; i < d / 2; i++)
                ans.push_back(go(ans.back(), -1, 1));
            ans.push_back(go(ans.back(), 0, 1));
            for (int i = 2; i < d / 2; i++)
                ans.push_back(go(ans.back(), 1, -1));
        }
    }
    else if (a >= 2) {
        for (int i = 0; i <= a / 2; i++)
            ans.push_back({ i, 0 });
        for (int i = a / 2; i >= 1; i--)
            ans.push_back({ i, 1 });
        for (int j = 2; j <= b / 2; j++)
            ans.push_back({ 1, j });
        for (int j = b / 2; j >= 1; j--)
            ans.push_back({ 0, j });
        if (d > c) {
            ans.push_back({ -1, 1 });
            vector<pair<int, int>> add;
            add.push_back({ 1, -1 });
            d -= 2;
            for (int i = 0; i < (d - c) / 2; i++)
                add.push_back({ i + 2, -i - 2 });
            for (int i = (d - c) / 2; i > 0; i--)
                add.push_back({ i + 1, -i });
            combine(ans, add, 0);
 
            d = c;
        }
        if (c > 0) {
            vector<pair<int, int>> add;
            for (int i = 0; i < c / 2 * 2; i++)
                add.push_back({ a / 2 + i + 1, 1 - (i % 2) });
            if (c & 1) {
                add.push_back(go(add.back(), 0, -1));
                add.push_back(go(add.back(), 1, 1));
            }
            for (int i = c / 2 * 2 - 1; i >= 0; i--)
                add.push_back({ add[i].first, add[i].second + 1 });
            combine(ans, add, indexof(ans, { a / 2, 0 }));
        }
    }
    else if (b >= 2) {
        if (d % 2 == 1) {
            for (int i = 0; i <= b / 2; i++)
                ans.push_back({ 0, i });
            for (int i = b / 2 - 1; i >= 0; i--)
                ans.push_back({ 1, i });
            for (int i = 0; i < (d - c) / 2; i++)
                ans.push_back(go(ans.back(), 1, -1));
            for (int i = 0; i < c / 2; i++) {
                ans.push_back(go(ans.back(), 1, -1));
                ans.push_back(go(ans.back(), -1, -1));
            }
            ans.push_back(go(ans.back(), -1, -1));
            ans.push_back(go(ans.back(), 0, 1));
            for (int i = 0; i < c / 2; i++) {
                ans.push_back(go(ans.back(), 1, 1));
                ans.push_back(go(ans.back(), -1, 1));
            }
            for (int i = 0; i < (d - c) / 2; i++)
                ans.push_back(go(ans.back(), -1, 1));
            if (ans.back() == make_pair(0, 0)) ans.pop_back();
        }
        else {
            for (int i = 0; i <= b / 2; i++)
                ans.push_back({ 0, i });
            ans.back().first++;
            for (int i = b / 2 - 1; i >= 0; i--)
                ans.push_back({ 1, i });
            for (int i = 0; i < (d - c) / 2; i++)
                ans.push_back(go(ans.back(), 1, -1));
            ans.push_back(go(ans.back(), 1, -1));
            for (int i = 0; i < c / 2 - 1; i++) {
                ans.push_back(go(ans.back(), 1, -1));
                ans.push_back(go(ans.back(), -1, -1));
            }
            ans.push_back(go(ans.back(), -1, -1));
            ans.push_back(go(ans.back(), 0, 1));
            for (int i = 0; i < c / 2 - 1; i++) {
                ans.push_back(go(ans.back(), 1, 1));
                ans.push_back(go(ans.back(), -1, 1));
            }
            ans.push_back(go(ans.back(), -1, 1));
            for (int i = 0; i < (d - c) / 2; i++)
                ans.push_back(go(ans.back(), -1, 1));
            if (ans.back() == make_pair(0, 0)) ans.pop_back();
        }
    }
    else {
        for (int i = 0; i <= d / 2; i++)
            ans.push_back({ i, -i });
        for (int i = d / 2; i > 0; i--)
            ans.push_back({ i + 1, -i + 1 });
        for (int i = 1; i < c / 2; i++)
            ans.push_back({ i + 2, i });
        for (int i = c / 2; i > 0; i--)
            ans.push_back({ i, i });
    }
    
}
 
int a, b, c, d;
bool doab = false, docd = false;
 
int main() {
    fast;
    cin >> a >> b >> c >> d;
    if (a > b) doab = true, swap(a, b);
    if (c > d) docd = true, swap(c, d);
 
    if (a == 1 && b == 1 && d == 1) {
        ans.push_back({ 0, 0 });
        ans.push_back({ 1, 0 });
        ans.push_back({ 0, 1 });
    }
    else if (a % 2 == 0) {
        solvecase1(a,b,c,d);
    }
    else {
        bool isc = false;
        --a, ++b;
        if (c & 1) --c, isc = true;
        else --d;
        if (a >= 2 || d > 0) {
            solvecase1(a, b, c, d);
            int ind = 0;
            for (int i = 0; i < ans.size(); i++)
                if (ans[i].first > ans[ind].first) ind = i;
            if (ans[ind].first != ans[ind + 1].first) ind--;
            vector<pair<int, int>> add;
            if (isc) {
                if (ans[ind].second < ans[ind + 1].second)
                    add.push_back(go(ans[ind], 1, 1));
                else
                    add.push_back(go(ans[ind], 1, 0));
            }
            else {
                if (ans[ind].second < ans[ind + 1].second)
                    add.push_back(go(ans[ind], 1, 0));
                else
                    add.push_back(go(ans[ind], 1, -1));
            }
            combine(ans, add, ind);
        }
    }
    if (doab) ab(ans);
    if (docd) cd(ans);
    if (ans.back() == make_pair(0, 0)) ans.pop_back();
    for (const auto &i : ans) cout << i.first << " " << i.second << endl;
}

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

pick.cpp: In function 'int main()':
pick.cpp:203:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < ans.size(); i++)
                             ~~^~~~~~~~~~~~
pick.cpp: In instantiation of 'void combine(std::vector<_Tp>&, std::vector<_Tp>&, int) [with T = std::pair<int, int>]':
pick.cpp:101:32:   required from here
pick.cpp:45:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (afterind + 1 < p.size()) tmp.push_back(p.back()), p.pop_back();
pick.cpp: In instantiation of 'int indexof(std::vector<_Tp>&, T) [with T = std::pair<int, int>]':
pick.cpp:115:56:   required from here
pick.cpp:37:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < p.size(); i++)

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 20 / 20