oj.uz

Submission #57743

# Submission time Handle Problem Language Result Execution time Memory
57743 2018-07-16T01:16:07 Z polyfish Pick (COI18_pick) C++14
80 / 100
 1000 ms 860 KB 
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define y1 _y1_
#define y2 _y2_

typedef pair<int, int> point;

class polygon {
public:
    vector<point> bound;

    void ins(point G) {
        bound.push_back(G);
    }

    int area() {
        int res = 0;
        for (int i=0; i<bound.size(); ++i) {
            int j = (i + 1 + bound.size()) % bound.size();
            res += (bound[i].x * bound[j].y - bound[i].y * bound[j].x);
        }
        return abs(res);
    }
} res;
int a, b, c, d;

void solve(int x1, int x2, int y1, int y2, int z1, int z2, int z3, int z4) {
    if (x1 + z2 + z3 != x2 + z1 + z4 || y1 + z1 + z2 != y2 + z3 + z4)
        return;
    polygon p;
    point cur(0, 0);
    p.ins(cur);
    for (int i=1; i<=x2; ++i) {
        --cur.x;
        p.ins(cur);
    }
    for (int i=1; i<=z1; ++i) {
        --cur.x;
        ++cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=z4; ++i) {
        --cur.x;
        --cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=y2; ++i) {
        --cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=z3; ++i) {
        ++cur.x;
        --cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=x1; ++i) {
        ++cur.x;
        p.ins(cur);
    }
    for (int i=1; i<=z2; ++i) {
        ++cur.x;
        ++cur.y;
        p.ins(cur);
    }
    for (int i=1; i<=y1; ++i) {
        ++cur.y;
        p.ins(cur);
    }
    if (cur != point(0, 0))
        return;
    p.bound.pop_back();
    if (res.bound.size()==0 || p.area()<res.area()) {
        res = p;
    }
}

int main() {
    //freopen("pick.inp", "r", stdin);
    //freopen("pick.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> a >> b >> c >> d;
    for (int x1=0; x1<=a; ++x1) {
        for (int y1=0; y1<=b; ++y1) {
            for (int z1=0; z1<=d; ++z1) {
                for (int z2=0; z2<=c; ++z2) {
                    int x2 = a - x1, y2 = b - y1, z3 = d - z1, z4 = c - z2;
                    solve(x1, x2, y1, y2, z1, z2, z3, z4);
                }
            }
        }
    }
    //cerr << res.area() << '\n';
    for (int i=0; i<(int)res.bound.size(); ++i)
        cout << res.bound[i].x << ' ' << res.bound[i].y << '\n';
}

Compilation message

pick.cpp: In member function 'int polygon::area()':
pick.cpp:21:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i=0; i<bound.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 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 516 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 3 ms 740 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 740 KB Output is correct
2 Correct 2 ms 740 KB Output is correct
3 Correct 3 ms 740 KB Output is correct
4 Correct 3 ms 740 KB Output is correct
5 Correct 2 ms 740 KB Output is correct
6 Correct 2 ms 740 KB Output is correct
7 Correct 2 ms 740 KB Output is correct
8 Correct 3 ms 740 KB Output is correct
9 Correct 3 ms 740 KB Output is correct
10 Correct 3 ms 740 KB Output is correct
11 Correct 3 ms 740 KB Output is correct
12 Correct 2 ms 740 KB Output is correct
13 Correct 2 ms 740 KB Output is correct
14 Correct 3 ms 740 KB Output is correct
15 Correct 3 ms 740 KB Output is correct
16 Correct 2 ms 740 KB Output is correct
17 Correct 3 ms 740 KB Output is correct
18 Correct 4 ms 740 KB Output is correct
19 Correct 6 ms 740 KB Output is correct
20 Correct 3 ms 740 KB Output is correct
21 Correct 3 ms 740 KB Output is correct
22 Correct 39 ms 740 KB Output is correct
23 Correct 7 ms 764 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 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 740 KB Output is correct
9 Correct 2 ms 740 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 3 ms 740 KB Output is correct
12 Correct 3 ms 740 KB Output is correct
13 Correct 2 ms 740 KB Output is correct
14 Correct 2 ms 740 KB Output is correct
15 Correct 2 ms 740 KB Output is correct
16 Correct 3 ms 740 KB Output is correct
17 Correct 3 ms 740 KB Output is correct
18 Correct 3 ms 740 KB Output is correct
19 Correct 3 ms 740 KB Output is correct
20 Correct 2 ms 740 KB Output is correct
21 Correct 2 ms 740 KB Output is correct
22 Correct 3 ms 740 KB Output is correct
23 Correct 3 ms 740 KB Output is correct
24 Correct 2 ms 740 KB Output is correct
25 Correct 3 ms 740 KB Output is correct
26 Correct 4 ms 740 KB Output is correct
27 Correct 6 ms 740 KB Output is correct
28 Correct 3 ms 740 KB Output is correct
29 Correct 3 ms 740 KB Output is correct
30 Correct 39 ms 740 KB Output is correct
31 Correct 7 ms 764 KB Output is correct
32 Correct 74 ms 764 KB Output is correct
33 Correct 48 ms 764 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 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 740 KB Output is correct
9 Correct 2 ms 740 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 3 ms 740 KB Output is correct
12 Correct 3 ms 740 KB Output is correct
13 Correct 2 ms 740 KB Output is correct
14 Correct 2 ms 740 KB Output is correct
15 Correct 2 ms 740 KB Output is correct
16 Correct 3 ms 740 KB Output is correct
17 Correct 3 ms 740 KB Output is correct
18 Correct 3 ms 740 KB Output is correct
19 Correct 3 ms 740 KB Output is correct
20 Correct 2 ms 740 KB Output is correct
21 Correct 2 ms 740 KB Output is correct
22 Correct 3 ms 740 KB Output is correct
23 Correct 3 ms 740 KB Output is correct
24 Correct 2 ms 740 KB Output is correct
25 Correct 3 ms 740 KB Output is correct
26 Correct 4 ms 740 KB Output is correct
27 Correct 6 ms 740 KB Output is correct
28 Correct 3 ms 740 KB Output is correct
29 Correct 3 ms 740 KB Output is correct
30 Correct 39 ms 740 KB Output is correct
31 Correct 7 ms 764 KB Output is correct
32 Correct 74 ms 764 KB Output is correct
33 Correct 48 ms 764 KB Output is correct
34 Correct 16 ms 764 KB Output is correct
35 Correct 197 ms 832 KB Output is correct
36 Correct 175 ms 848 KB Output is correct

Subtask #10
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 436 KB Output is correct
4 Correct 2 ms 436 KB Output is correct
5 Correct 2 ms 516 KB Output is correct
6 Correct 2 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 3 ms 740 KB Output is correct
9 Correct 2 ms 740 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 3 ms 740 KB Output is correct
12 Correct 3 ms 740 KB Output is correct
13 Correct 2 ms 740 KB Output is correct
14 Correct 2 ms 740 KB Output is correct
15 Correct 2 ms 740 KB Output is correct
16 Correct 3 ms 740 KB Output is correct
17 Correct 3 ms 740 KB Output is correct
18 Correct 3 ms 740 KB Output is correct
19 Correct 3 ms 740 KB Output is correct
20 Correct 2 ms 740 KB Output is correct
21 Correct 2 ms 740 KB Output is correct
22 Correct 3 ms 740 KB Output is correct
23 Correct 3 ms 740 KB Output is correct
24 Correct 2 ms 740 KB Output is correct
25 Correct 3 ms 740 KB Output is correct
26 Correct 4 ms 740 KB Output is correct
27 Correct 6 ms 740 KB Output is correct
28 Correct 3 ms 740 KB Output is correct
29 Correct 3 ms 740 KB Output is correct
30 Correct 39 ms 740 KB Output is correct
31 Correct 7 ms 764 KB Output is correct
32 Correct 74 ms 764 KB Output is correct
33 Correct 48 ms 764 KB Output is correct
34 Correct 16 ms 764 KB Output is correct
35 Correct 197 ms 832 KB Output is correct
36 Correct 175 ms 848 KB Output is correct
37 Correct 185 ms 860 KB Output is correct
38 Correct 298 ms 860 KB Output is correct
39 Execution timed out 1080 ms 860 KB Time limit exceeded
40 Halted 0 ms 0 KB -