oj.uz

Submission #57742

# Submission time Handle Problem Language Result Execution time Memory
57742 2018-07-16T01:13:30 Z polyfish Pick (COI18_pick) C++14
50 / 100
 1000 ms 924 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) {
    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 480 KB Output is correct
4 Correct 19 ms 484 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 3 ms 600 KB Output is correct
3 Correct 2 ms 648 KB Output is correct
4 Correct 24 ms 712 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 712 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 780 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 3 ms 788 KB Output is correct
7 Correct 3 ms 792 KB Output is correct
8 Correct 2 ms 812 KB Output is correct
9 Correct 2 ms 924 KB Output is correct
10 Correct 3 ms 924 KB Output is correct
11 Correct 2 ms 924 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 712 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 780 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 3 ms 788 KB Output is correct
7 Correct 3 ms 792 KB Output is correct
8 Correct 2 ms 812 KB Output is correct
9 Correct 2 ms 924 KB Output is correct
10 Correct 3 ms 924 KB Output is correct
11 Correct 2 ms 924 KB Output is correct
12 Correct 2 ms 924 KB Output is correct
13 Correct 2 ms 924 KB Output is correct
14 Correct 3 ms 924 KB Output is correct
15 Correct 4 ms 924 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 712 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 780 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 3 ms 788 KB Output is correct
7 Correct 3 ms 792 KB Output is correct
8 Correct 2 ms 812 KB Output is correct
9 Correct 2 ms 924 KB Output is correct
10 Correct 3 ms 924 KB Output is correct
11 Correct 2 ms 924 KB Output is correct
12 Correct 2 ms 924 KB Output is correct
13 Correct 2 ms 924 KB Output is correct
14 Correct 3 ms 924 KB Output is correct
15 Correct 4 ms 924 KB Output is correct
16 Correct 23 ms 924 KB Output is correct
17 Correct 24 ms 924 KB Output is correct
18 Correct 8 ms 924 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 712 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 780 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 3 ms 788 KB Output is correct
7 Correct 3 ms 792 KB Output is correct
8 Correct 2 ms 812 KB Output is correct
9 Correct 2 ms 924 KB Output is correct
10 Correct 3 ms 924 KB Output is correct
11 Correct 2 ms 924 KB Output is correct
12 Correct 2 ms 924 KB Output is correct
13 Correct 2 ms 924 KB Output is correct
14 Correct 3 ms 924 KB Output is correct
15 Correct 4 ms 924 KB Output is correct
16 Correct 23 ms 924 KB Output is correct
17 Correct 24 ms 924 KB Output is correct
18 Correct 8 ms 924 KB Output is correct
19 Correct 266 ms 924 KB Output is correct
20 Correct 53 ms 924 KB Output is correct
21 Correct 25 ms 924 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 712 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 780 KB Output is correct
5 Correct 2 ms 784 KB Output is correct
6 Correct 3 ms 788 KB Output is correct
7 Correct 3 ms 792 KB Output is correct
8 Correct 2 ms 812 KB Output is correct
9 Correct 2 ms 924 KB Output is correct
10 Correct 3 ms 924 KB Output is correct
11 Correct 2 ms 924 KB Output is correct
12 Correct 2 ms 924 KB Output is correct
13 Correct 2 ms 924 KB Output is correct
14 Correct 3 ms 924 KB Output is correct
15 Correct 4 ms 924 KB Output is correct
16 Correct 23 ms 924 KB Output is correct
17 Correct 24 ms 924 KB Output is correct
18 Correct 8 ms 924 KB Output is correct
19 Correct 266 ms 924 KB Output is correct
20 Correct 53 ms 924 KB Output is correct
21 Correct 25 ms 924 KB Output is correct
22 Execution timed out 1074 ms 924 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #8
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 480 KB Output is correct
4 Correct 19 ms 484 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 24 ms 712 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 780 KB Output is correct
13 Correct 2 ms 784 KB Output is correct
14 Correct 3 ms 788 KB Output is correct
15 Correct 3 ms 792 KB Output is correct
16 Correct 2 ms 812 KB Output is correct
17 Correct 2 ms 924 KB Output is correct
18 Correct 3 ms 924 KB Output is correct
19 Correct 2 ms 924 KB Output is correct
20 Correct 2 ms 924 KB Output is correct
21 Correct 2 ms 924 KB Output is correct
22 Correct 3 ms 924 KB Output is correct
23 Correct 4 ms 924 KB Output is correct
24 Correct 23 ms 924 KB Output is correct
25 Correct 24 ms 924 KB Output is correct
26 Correct 8 ms 924 KB Output is correct
27 Correct 266 ms 924 KB Output is correct
28 Correct 53 ms 924 KB Output is correct
29 Correct 25 ms 924 KB Output is correct
30 Execution timed out 1074 ms 924 KB Time limit exceeded
31 Halted 0 ms 0 KB -

Subtask #9
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 480 KB Output is correct
4 Correct 19 ms 484 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 24 ms 712 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 780 KB Output is correct
13 Correct 2 ms 784 KB Output is correct
14 Correct 3 ms 788 KB Output is correct
15 Correct 3 ms 792 KB Output is correct
16 Correct 2 ms 812 KB Output is correct
17 Correct 2 ms 924 KB Output is correct
18 Correct 3 ms 924 KB Output is correct
19 Correct 2 ms 924 KB Output is correct
20 Correct 2 ms 924 KB Output is correct
21 Correct 2 ms 924 KB Output is correct
22 Correct 3 ms 924 KB Output is correct
23 Correct 4 ms 924 KB Output is correct
24 Correct 23 ms 924 KB Output is correct
25 Correct 24 ms 924 KB Output is correct
26 Correct 8 ms 924 KB Output is correct
27 Correct 266 ms 924 KB Output is correct
28 Correct 53 ms 924 KB Output is correct
29 Correct 25 ms 924 KB Output is correct
30 Execution timed out 1074 ms 924 KB Time limit exceeded
31 Halted 0 ms 0 KB -

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 480 KB Output is correct
4 Correct 19 ms 484 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 2 ms 648 KB Output is correct
8 Correct 24 ms 712 KB Output is correct
9 Correct 2 ms 712 KB Output is correct
10 Correct 2 ms 752 KB Output is correct
11 Correct 2 ms 760 KB Output is correct
12 Correct 2 ms 780 KB Output is correct
13 Correct 2 ms 784 KB Output is correct
14 Correct 3 ms 788 KB Output is correct
15 Correct 3 ms 792 KB Output is correct
16 Correct 2 ms 812 KB Output is correct
17 Correct 2 ms 924 KB Output is correct
18 Correct 3 ms 924 KB Output is correct
19 Correct 2 ms 924 KB Output is correct
20 Correct 2 ms 924 KB Output is correct
21 Correct 2 ms 924 KB Output is correct
22 Correct 3 ms 924 KB Output is correct
23 Correct 4 ms 924 KB Output is correct
24 Correct 23 ms 924 KB Output is correct
25 Correct 24 ms 924 KB Output is correct
26 Correct 8 ms 924 KB Output is correct
27 Correct 266 ms 924 KB Output is correct
28 Correct 53 ms 924 KB Output is correct
29 Correct 25 ms 924 KB Output is correct
30 Execution timed out 1074 ms 924 KB Time limit exceeded
31 Halted 0 ms 0 KB -