oj.uz

Submission #527781

# Submission time Handle Problem Language Result Execution time Memory
527781 2022-02-18T09:21:15 Z boris_mihov Diamond Hands (innopolis2021_final_B) C++14
24 / 100
 47 ms 1868 KB 
#include <iostream>
#include <vector>
#include <cassert>
const int maxn = 2e5+10;

int n;
std::pair < int, int > d[maxn];
std::vector < std::pair < int, char > > ans;

void invalid() {

    std::cout << -1 << '\n';
    exit(0);

}

void solve() {

    for (int i = 1 ; i <= n ; ++i) {

        int diff = d[i].first - d[i-1].first;
        int desired = d[i].second - d[i-1].second;
        if (!(-diff <= desired && desired <= diff && (diff - desired) % 2 == 0)) invalid();

        if (desired == diff) {

            if (i == 2 && ans.size() == 2) swap(ans.front(), ans.back());
            if (!ans.empty() && ans.back().second == '+') ans.back().first += diff;
            else ans.push_back({diff, '+'});
            continue;

        }

        if (desired == -diff) {

            if (!ans.empty() && ans.back().second == '-') ans.back().first += diff;
            else ans.push_back({diff, '-'}); 
            continue;          

        }

        int subtract = (diff - desired) / 2;
        int add = diff - subtract;

        if (i == 1) {

            ans.push_back({add, '+'});
            ans.push_back({subtract, '-'});
            continue;

        }

        if (ans.back().second == '+') {

            ans.back().first += add;
            ans.push_back({subtract, '-'});
            continue;

        }

        ans.back().first += subtract;
        ans.push_back({add, '+'});

    }

    std::cout << ans.size() << '\n';
    for (int i = 0 ; i < ans.size() ; ++i)
        std::cout << ans[i].first << ' ' << ans[i].second << '\n';

    for (int i = 0 ; i < ans.size()-1 ; ++i)
        assert(ans[i].second != ans[i+1].second);

}

void read() {

    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
        std::cin >> d[i].first >> d[i].second;

}

void fast_io() {

    std::ios_base :: sync_with_stdio(0);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

}

int t;
int main () {

    fast_io();
    read();
    solve();

    return 0;

}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:67:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |     for (int i = 0 ; i < ans.size() ; ++i)
      |                      ~~^~~~~~~~~~~~
Main.cpp:70:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for (int i = 0 ; i < ans.size()-1 ; ++i)
      |                      ~~^~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB OK, n=2 ans=1
2 Correct 0 ms 204 KB OK, n=3 ans=1
3 Correct 0 ms 204 KB OK, n=1 ans=1
4 Correct 0 ms 204 KB OK, n=5 ans=1
5 Correct 0 ms 204 KB OK, n=8 ans=1
6 Correct 0 ms 204 KB OK, n=88 ans=1
7 Correct 0 ms 204 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 332 KB OK, n=2000 ans=1
10 Correct 1 ms 212 KB OK, n=2000 ans=1
11 Correct 1 ms 332 KB OK, n=2000 ans=1
12 Correct 0 ms 204 KB OK, n=2 ans=1
13 Correct 0 ms 204 KB OK, n=34 ans=1
14 Correct 1 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 1 ms 204 KB OK, no solution, n=2
17 Correct 1 ms 204 KB OK, no solution, n=3
18 Correct 1 ms 204 KB OK, no solution, n=40
19 Correct 1 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB OK, n=2 ans=1
2 Correct 0 ms 204 KB OK, n=3 ans=1
3 Correct 0 ms 204 KB OK, n=1 ans=1
4 Correct 0 ms 204 KB OK, n=5 ans=1
5 Correct 0 ms 204 KB OK, n=8 ans=1
6 Correct 0 ms 204 KB OK, n=88 ans=1
7 Correct 0 ms 204 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 332 KB OK, n=2000 ans=1
10 Correct 1 ms 212 KB OK, n=2000 ans=1
11 Correct 1 ms 332 KB OK, n=2000 ans=1
12 Correct 0 ms 204 KB OK, n=2 ans=1
13 Correct 0 ms 204 KB OK, n=34 ans=1
14 Correct 1 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 1 ms 204 KB OK, no solution, n=2
17 Correct 1 ms 204 KB OK, no solution, n=3
18 Correct 1 ms 204 KB OK, no solution, n=40
19 Correct 1 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000
22 Correct 0 ms 204 KB OK, n=2 ans=2
23 Correct 0 ms 204 KB OK, n=3 ans=2
24 Correct 0 ms 204 KB OK, n=4 ans=1
25 Correct 0 ms 204 KB OK, n=5 ans=2
26 Correct 1 ms 204 KB OK, n=8 ans=2
27 Correct 0 ms 204 KB OK, n=88 ans=2
28 Correct 1 ms 332 KB OK, n=888 ans=2
29 Correct 1 ms 332 KB OK, n=2000 ans=2
30 Correct 1 ms 332 KB OK, n=2000 ans=2
31 Correct 1 ms 332 KB OK, n=2000 ans=2
32 Correct 1 ms 332 KB OK, n=2000 ans=2
33 Correct 0 ms 204 KB OK, n=2 ans=1
34 Correct 0 ms 204 KB OK, n=34 ans=2
35 Correct 1 ms 204 KB OK, n=567 ans=2
36 Correct 1 ms 204 KB OK, n=1234 ans=2
37 Correct 1 ms 204 KB OK, no solution, n=6
38 Correct 1 ms 204 KB OK, no solution, n=10
39 Correct 1 ms 204 KB OK, no solution, n=50
40 Correct 1 ms 204 KB OK, no solution, n=333
41 Correct 1 ms 332 KB OK, no solution, n=2000
42 Correct 1 ms 332 KB OK, no solution, n=2000
43 Correct 0 ms 204 KB OK, n=1 ans=2
44 Correct 0 ms 204 KB OK, n=1 ans=2

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB OK, n=2 ans=1
2 Correct 0 ms 204 KB OK, n=3 ans=1
3 Correct 0 ms 204 KB OK, n=1 ans=1
4 Correct 0 ms 204 KB OK, n=5 ans=1
5 Correct 0 ms 204 KB OK, n=8 ans=1
6 Correct 0 ms 204 KB OK, n=88 ans=1
7 Correct 0 ms 204 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 332 KB OK, n=2000 ans=1
10 Correct 1 ms 212 KB OK, n=2000 ans=1
11 Correct 1 ms 332 KB OK, n=2000 ans=1
12 Correct 0 ms 204 KB OK, n=2 ans=1
13 Correct 0 ms 204 KB OK, n=34 ans=1
14 Correct 1 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 1 ms 204 KB OK, no solution, n=2
17 Correct 1 ms 204 KB OK, no solution, n=3
18 Correct 1 ms 204 KB OK, no solution, n=40
19 Correct 1 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000
22 Correct 0 ms 204 KB OK, n=4 ans=2
23 Correct 0 ms 204 KB OK, n=6 ans=2
24 Correct 0 ms 204 KB OK, n=15 ans=2
25 Correct 0 ms 204 KB OK, n=200 ans=2
26 Correct 1 ms 204 KB OK, n=1000 ans=2
27 Correct 2 ms 332 KB OK, n=10000 ans=2
28 Correct 15 ms 972 KB OK, n=100000 ans=2
29 Correct 23 ms 1500 KB OK, n=159807 ans=2
30 Correct 28 ms 1868 KB OK, n=200000 ans=2
31 Correct 32 ms 1800 KB OK, n=200000 ans=2
32 Correct 47 ms 1784 KB OK, n=200000 ans=2
33 Correct 0 ms 204 KB OK, n=3 ans=2
34 Correct 1 ms 204 KB OK, n=45 ans=2
35 Correct 1 ms 204 KB OK, n=789 ans=2
36 Correct 1 ms 204 KB OK, n=2345 ans=2
37 Correct 11 ms 844 KB OK, n=67890 ans=2
38 Correct 24 ms 1508 KB OK, no solution, n=159807
39 Correct 29 ms 1852 KB OK, no solution, n=200000
40 Correct 31 ms 1836 KB OK, no solution, n=200000
41 Correct 34 ms 1748 KB OK, no solution, n=200000

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB OK, n=5 ans=3
2 Correct 1 ms 204 KB OK, n=10 ans=4
3 Correct 1 ms 204 KB OK, n=20 ans=5
4 Correct 1 ms 204 KB OK, n=50 ans=9
5 Correct 1 ms 204 KB OK, n=100 ans=18
6 Correct 0 ms 204 KB OK, n=200 ans=46
7 Correct 0 ms 204 KB OK, n=100 ans=5
8 Correct 0 ms 204 KB OK, n=200 ans=20
9 Correct 1 ms 204 KB OK, n=400 ans=76
10 Correct 0 ms 204 KB OK, n=1000 ans=196
11 Correct 0 ms 332 KB OK, n=1000 ans=434
12 Correct 1 ms 332 KB OK, n=1000 ans=582
13 Correct 1 ms 332 KB OK, n=1000 ans=798
14 Incorrect 1 ms 332 KB WA, participant didn't the optimal solution n=1000 ans=867 part=868
15 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB OK, n=2 ans=1
2 Correct 0 ms 204 KB OK, n=3 ans=1
3 Correct 0 ms 204 KB OK, n=1 ans=1
4 Correct 0 ms 204 KB OK, n=5 ans=1
5 Correct 0 ms 204 KB OK, n=8 ans=1
6 Correct 0 ms 204 KB OK, n=88 ans=1
7 Correct 0 ms 204 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 332 KB OK, n=2000 ans=1
10 Correct 1 ms 212 KB OK, n=2000 ans=1
11 Correct 1 ms 332 KB OK, n=2000 ans=1
12 Correct 0 ms 204 KB OK, n=2 ans=1
13 Correct 0 ms 204 KB OK, n=34 ans=1
14 Correct 1 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 1 ms 204 KB OK, no solution, n=2
17 Correct 1 ms 204 KB OK, no solution, n=3
18 Correct 1 ms 204 KB OK, no solution, n=40
19 Correct 1 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000
22 Correct 0 ms 204 KB OK, n=2 ans=2
23 Correct 0 ms 204 KB OK, n=3 ans=2
24 Correct 0 ms 204 KB OK, n=4 ans=1
25 Correct 0 ms 204 KB OK, n=5 ans=2
26 Correct 1 ms 204 KB OK, n=8 ans=2
27 Correct 0 ms 204 KB OK, n=88 ans=2
28 Correct 1 ms 332 KB OK, n=888 ans=2
29 Correct 1 ms 332 KB OK, n=2000 ans=2
30 Correct 1 ms 332 KB OK, n=2000 ans=2
31 Correct 1 ms 332 KB OK, n=2000 ans=2
32 Correct 1 ms 332 KB OK, n=2000 ans=2
33 Correct 0 ms 204 KB OK, n=2 ans=1
34 Correct 0 ms 204 KB OK, n=34 ans=2
35 Correct 1 ms 204 KB OK, n=567 ans=2
36 Correct 1 ms 204 KB OK, n=1234 ans=2
37 Correct 1 ms 204 KB OK, no solution, n=6
38 Correct 1 ms 204 KB OK, no solution, n=10
39 Correct 1 ms 204 KB OK, no solution, n=50
40 Correct 1 ms 204 KB OK, no solution, n=333
41 Correct 1 ms 332 KB OK, no solution, n=2000
42 Correct 1 ms 332 KB OK, no solution, n=2000
43 Correct 0 ms 204 KB OK, n=1 ans=2
44 Correct 0 ms 204 KB OK, n=1 ans=2
45 Correct 0 ms 204 KB OK, n=5 ans=3
46 Correct 1 ms 204 KB OK, n=10 ans=4
47 Correct 1 ms 204 KB OK, n=20 ans=5
48 Correct 1 ms 204 KB OK, n=50 ans=9
49 Correct 1 ms 204 KB OK, n=100 ans=18
50 Correct 0 ms 204 KB OK, n=200 ans=46
51 Correct 0 ms 204 KB OK, n=100 ans=5
52 Correct 0 ms 204 KB OK, n=200 ans=20
53 Correct 1 ms 204 KB OK, n=400 ans=76
54 Correct 0 ms 204 KB OK, n=1000 ans=196
55 Correct 0 ms 332 KB OK, n=1000 ans=434
56 Correct 1 ms 332 KB OK, n=1000 ans=582
57 Correct 1 ms 332 KB OK, n=1000 ans=798
58 Incorrect 1 ms 332 KB WA, participant didn't the optimal solution n=1000 ans=867 part=868
59 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB OK, n=2 ans=1
2 Correct 0 ms 204 KB OK, n=3 ans=1
3 Correct 0 ms 204 KB OK, n=1 ans=1
4 Correct 0 ms 204 KB OK, n=5 ans=1
5 Correct 0 ms 204 KB OK, n=8 ans=1
6 Correct 0 ms 204 KB OK, n=88 ans=1
7 Correct 0 ms 204 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 332 KB OK, n=2000 ans=1
10 Correct 1 ms 212 KB OK, n=2000 ans=1
11 Correct 1 ms 332 KB OK, n=2000 ans=1
12 Correct 0 ms 204 KB OK, n=2 ans=1
13 Correct 0 ms 204 KB OK, n=34 ans=1
14 Correct 1 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 1 ms 204 KB OK, no solution, n=2
17 Correct 1 ms 204 KB OK, no solution, n=3
18 Correct 1 ms 204 KB OK, no solution, n=40
19 Correct 1 ms 204 KB OK, no solution, n=118
20 Correct 1 ms 332 KB OK, no solution, n=2000
21 Correct 1 ms 332 KB OK, no solution, n=2000
22 Correct 0 ms 204 KB OK, n=2 ans=2
23 Correct 0 ms 204 KB OK, n=3 ans=2
24 Correct 0 ms 204 KB OK, n=4 ans=1
25 Correct 0 ms 204 KB OK, n=5 ans=2
26 Correct 1 ms 204 KB OK, n=8 ans=2
27 Correct 0 ms 204 KB OK, n=88 ans=2
28 Correct 1 ms 332 KB OK, n=888 ans=2
29 Correct 1 ms 332 KB OK, n=2000 ans=2
30 Correct 1 ms 332 KB OK, n=2000 ans=2
31 Correct 1 ms 332 KB OK, n=2000 ans=2
32 Correct 1 ms 332 KB OK, n=2000 ans=2
33 Correct 0 ms 204 KB OK, n=2 ans=1
34 Correct 0 ms 204 KB OK, n=34 ans=2
35 Correct 1 ms 204 KB OK, n=567 ans=2
36 Correct 1 ms 204 KB OK, n=1234 ans=2
37 Correct 1 ms 204 KB OK, no solution, n=6
38 Correct 1 ms 204 KB OK, no solution, n=10
39 Correct 1 ms 204 KB OK, no solution, n=50
40 Correct 1 ms 204 KB OK, no solution, n=333
41 Correct 1 ms 332 KB OK, no solution, n=2000
42 Correct 1 ms 332 KB OK, no solution, n=2000
43 Correct 0 ms 204 KB OK, n=1 ans=2
44 Correct 0 ms 204 KB OK, n=1 ans=2
45 Correct 0 ms 204 KB OK, n=4 ans=2
46 Correct 0 ms 204 KB OK, n=6 ans=2
47 Correct 0 ms 204 KB OK, n=15 ans=2
48 Correct 0 ms 204 KB OK, n=200 ans=2
49 Correct 1 ms 204 KB OK, n=1000 ans=2
50 Correct 2 ms 332 KB OK, n=10000 ans=2
51 Correct 15 ms 972 KB OK, n=100000 ans=2
52 Correct 23 ms 1500 KB OK, n=159807 ans=2
53 Correct 28 ms 1868 KB OK, n=200000 ans=2
54 Correct 32 ms 1800 KB OK, n=200000 ans=2
55 Correct 47 ms 1784 KB OK, n=200000 ans=2
56 Correct 0 ms 204 KB OK, n=3 ans=2
57 Correct 1 ms 204 KB OK, n=45 ans=2
58 Correct 1 ms 204 KB OK, n=789 ans=2
59 Correct 1 ms 204 KB OK, n=2345 ans=2
60 Correct 11 ms 844 KB OK, n=67890 ans=2
61 Correct 24 ms 1508 KB OK, no solution, n=159807
62 Correct 29 ms 1852 KB OK, no solution, n=200000
63 Correct 31 ms 1836 KB OK, no solution, n=200000
64 Correct 34 ms 1748 KB OK, no solution, n=200000
65 Correct 0 ms 204 KB OK, n=5 ans=3
66 Correct 1 ms 204 KB OK, n=10 ans=4
67 Correct 1 ms 204 KB OK, n=20 ans=5
68 Correct 1 ms 204 KB OK, n=50 ans=9
69 Correct 1 ms 204 KB OK, n=100 ans=18
70 Correct 0 ms 204 KB OK, n=200 ans=46
71 Correct 0 ms 204 KB OK, n=100 ans=5
72 Correct 0 ms 204 KB OK, n=200 ans=20
73 Correct 1 ms 204 KB OK, n=400 ans=76
74 Correct 0 ms 204 KB OK, n=1000 ans=196
75 Correct 0 ms 332 KB OK, n=1000 ans=434
76 Correct 1 ms 332 KB OK, n=1000 ans=582
77 Correct 1 ms 332 KB OK, n=1000 ans=798
78 Incorrect 1 ms 332 KB WA, participant didn't the optimal solution n=1000 ans=867 part=868
79 Halted 0 ms 0 KB -