oj.uz

Submission #44073

# Submission time Handle Problem Language Result Execution time Memory
44073 2018-03-29T15:55:40 Z Noam527 Pick (COI18_pick) C++17
100 / 100
 3 ms 860 KB 
#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;
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 480 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 480 KB Output is correct
2 Correct 2 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 528 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 696 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 696 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 696 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 696 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 2 ms 860 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 568 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 2 ms 696 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 2 ms 696 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 2 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 860 KB Output is correct
13 Correct 2 ms 860 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 2 ms 860 KB Output is correct
23 Correct 2 ms 860 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 480 KB Output is correct
7 Correct 2 ms 480 KB Output is correct
8 Correct 2 ms 528 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 2 ms 696 KB Output is correct
12 Correct 2 ms 696 KB Output is correct
13 Correct 2 ms 696 KB Output is correct
14 Correct 2 ms 696 KB Output is correct
15 Correct 2 ms 696 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 2 ms 860 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 860 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 860 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 2 ms 860 KB Output is correct
33 Correct 2 ms 860 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 480 KB Output is correct
7 Correct 2 ms 480 KB Output is correct
8 Correct 2 ms 528 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 2 ms 696 KB Output is correct
12 Correct 2 ms 696 KB Output is correct
13 Correct 2 ms 696 KB Output is correct
14 Correct 2 ms 696 KB Output is correct
15 Correct 2 ms 696 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 2 ms 860 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 860 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 860 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 2 ms 860 KB Output is correct
33 Correct 2 ms 860 KB Output is correct
34 Correct 2 ms 860 KB Output is correct
35 Correct 2 ms 860 KB Output is correct
36 Correct 2 ms 860 KB Output is correct

Subtask #10
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 428 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 480 KB Output is correct
7 Correct 2 ms 480 KB Output is correct
8 Correct 2 ms 528 KB Output is correct
9 Correct 2 ms 568 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 2 ms 696 KB Output is correct
12 Correct 2 ms 696 KB Output is correct
13 Correct 2 ms 696 KB Output is correct
14 Correct 2 ms 696 KB Output is correct
15 Correct 2 ms 696 KB Output is correct
16 Correct 2 ms 860 KB Output is correct
17 Correct 2 ms 860 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 2 ms 860 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 2 ms 860 KB Output is correct
22 Correct 2 ms 860 KB Output is correct
23 Correct 2 ms 860 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 2 ms 860 KB Output is correct
26 Correct 2 ms 860 KB Output is correct
27 Correct 2 ms 860 KB Output is correct
28 Correct 2 ms 860 KB Output is correct
29 Correct 2 ms 860 KB Output is correct
30 Correct 2 ms 860 KB Output is correct
31 Correct 2 ms 860 KB Output is correct
32 Correct 2 ms 860 KB Output is correct
33 Correct 2 ms 860 KB Output is correct
34 Correct 2 ms 860 KB Output is correct
35 Correct 2 ms 860 KB Output is correct
36 Correct 2 ms 860 KB Output is correct
37 Correct 2 ms 860 KB Output is correct
38 Correct 2 ms 860 KB Output is correct
39 Correct 2 ms 860 KB Output is correct
40 Correct 2 ms 860 KB Output is correct
41 Correct 3 ms 860 KB Output is correct
42 Correct 2 ms 860 KB Output is correct
43 Correct 2 ms 860 KB Output is correct