oj.uz

Submission #527788

# Submission time Handle Problem Language Result Execution time Memory
527788 2022-02-18T09:32:52 Z boris_mihov Diamond Hands (innopolis2021_final_B) C++14
16 / 100
 39 ms 2000 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 332 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 216 KB OK, n=2000 ans=1
10 Correct 1 ms 332 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 0 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 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
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 332 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 216 KB OK, n=2000 ans=1
10 Correct 1 ms 332 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 0 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 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 0 ms 204 KB OK, n=8 ans=2
27 Correct 0 ms 204 KB OK, n=88 ans=2
28 Correct 0 ms 204 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 Incorrect 0 ms 204 KB WA, participant didn't the optimal solution n=34 ans=2 part=3
35 Halted 0 ms 0 KB -

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 332 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 216 KB OK, n=2000 ans=1
10 Correct 1 ms 332 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 0 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 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 1 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 1060 KB OK, n=100000 ans=2
29 Correct 22 ms 1476 KB OK, n=159807 ans=2
30 Correct 28 ms 1868 KB OK, n=200000 ans=2
31 Correct 31 ms 1804 KB OK, n=200000 ans=2
32 Correct 34 ms 1776 KB OK, n=200000 ans=2
33 Correct 0 ms 204 KB OK, n=3 ans=2
34 Correct 0 ms 204 KB OK, n=45 ans=2
35 Correct 1 ms 204 KB OK, n=789 ans=2
36 Correct 1 ms 332 KB OK, n=2345 ans=2
37 Correct 11 ms 844 KB OK, n=67890 ans=2
38 Correct 23 ms 1532 KB OK, no solution, n=159807
39 Correct 29 ms 1872 KB OK, no solution, n=200000
40 Correct 31 ms 1824 KB OK, no solution, n=200000
41 Correct 39 ms 2000 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 0 ms 204 KB OK, n=10 ans=4
3 Correct 0 ms 204 KB OK, n=20 ans=5
4 Correct 0 ms 204 KB OK, n=50 ans=9
5 Correct 1 ms 208 KB OK, n=100 ans=18
6 Correct 1 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 1 ms 332 KB OK, n=1000 ans=196
11 Incorrect 1 ms 332 KB WA, participant didn't the optimal solution n=1000 ans=434 part=435
12 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 332 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 216 KB OK, n=2000 ans=1
10 Correct 1 ms 332 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 0 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 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 0 ms 204 KB OK, n=8 ans=2
27 Correct 0 ms 204 KB OK, n=88 ans=2
28 Correct 0 ms 204 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 Incorrect 0 ms 204 KB WA, participant didn't the optimal solution n=34 ans=2 part=3
35 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 332 KB OK, n=888 ans=1
8 Correct 1 ms 332 KB OK, n=2000 ans=1
9 Correct 1 ms 216 KB OK, n=2000 ans=1
10 Correct 1 ms 332 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 0 ms 204 KB OK, n=567 ans=1
15 Correct 1 ms 204 KB OK, n=1234 ans=1
16 Correct 0 ms 204 KB OK, no solution, n=2
17 Correct 0 ms 204 KB OK, no solution, n=3
18 Correct 0 ms 204 KB OK, no solution, n=40
19 Correct 0 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 0 ms 204 KB OK, n=8 ans=2
27 Correct 0 ms 204 KB OK, n=88 ans=2
28 Correct 0 ms 204 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 Incorrect 0 ms 204 KB WA, participant didn't the optimal solution n=34 ans=2 part=3
35 Halted 0 ms 0 KB -