oj.uz

Submission #1079385

# Submission time Handle Problem Language Result Execution time Memory
1079385 2024-08-28T13:46:16 Z boris_mihov JOIRIS (JOI16_joiris) C++17
30 / 100
 1 ms 600 KB 
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <chrono>
#include <random>
#include <ctime>
#include <map>

typedef long long llong;
const int MAXN = 1000 + 10;
const int INF = 1e9;

int n, k;
int a[MAXN];
int b[MAXN];
std::vector <std::pair <int,int>> ops;

void solve()
{
    ops.clear();
    int sum = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        sum += a[i];
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        b[i] = a[i];
    }

    sum %= n;
    bool isOk = false;
    for (int i = 1 ; i <= n ; ++i)
    {
        if ((k * i + sum) % n == 0)
        {
            isOk = true;
            break;
        }
    }

    if (!isOk)
    {
        std::cout << -1 << '\n';
        exit(0);
    }

    int max = 0;
    for (int i = 1 ; i <= n ; ++i)
    {
        max = std::max(max, a[i]);
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        while (a[i] < max)
        {
            a[i] += k;
            ops.push_back({1, i});
        }
    }

    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] -= max;
    }

    // std::cerr << "at the begining: " << ops.size() << "\n";
    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     std::cerr << a[i] << ' ';
    // }

    // std::cerr << '\n';

    int time_to_add;
    bool wasEven = (n % 2 == 0);
    // k = 2 from now on
    if (wasEven)
    {
        time_to_add = ops.size();
        n--;
    }

    int times = 0;
    for (int i = 1 ; i + 1 <= n ; ++i)
    {
        if (a[i] == 0 && a[i + 1] == 0)
        {
            ops.push_back({2, i});
            a[i]++; a[i + 1]++;
            i++;
        }
    }

    for (int i = 1 ; i <= n ; i += 2)
    {
        if (a[i] == 0)
        {
            ops.push_back({1, i});
            for (int j = 1 ; j < i ; j += 2)
            {
                ops.push_back({2, j});
            }

            for (int j = i + 1 ; j < n ; j += 2)
            {
                ops.push_back({2, j});
            }

            a[i]++;
            times++;
        }
    }

    for (int i = 2 ; i <= n ; i += 2)
    {
        if (a[i] == 0)
        {
            ops.push_back({1, i});
            a[i] += 2;
        }
    }

    times++;
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i]--;
    }

    for (int i = 1 ; i + 1 <= n ; ++i)
    {
        if (a[i] == 0 && a[i + 1] == 0)
        {
            ops.push_back({2, i});
            a[i]++; a[i + 1]++;
            i++;
        }
    }

    for (int i = 1 ; i <= n ; i += 2)
    {
        if (a[i] == 0)
        {
            ops.push_back({1, i});
            for (int j = 1 ; j < i ; j += 2)
            {
                ops.push_back({2, j});
            }

            for (int j = i + 1 ; j < n ; j += 2)
            {
                ops.push_back({2, j});
            }

            a[i]++;
            times++;
        }
    }

    if (wasEven)
    {
        n++;
        for (const auto &[t, x] : ops)
        {
            if (t == 1) b[x] += 2;
            else
            {
                b[x]++;
                b[x + 1]++;
            }
        }
        
        std::vector <std::pair <int,int>> popped;
        while (ops.size() > time_to_add)
        {
            popped.push_back(ops.back());
            ops.pop_back();
        }
 
        while (b[n] < b[1])
        {
            b[n] += 2;
            ops.push_back({1, n});
        }

        while (popped.size())
        {
            ops.push_back(popped.back());
            popped.pop_back();
        }
    }

    // std::cout << "done\n";
    // std::cerr << "at the end\n";
    // for (int i = 1 ; i <= n ; ++i)
    // {
    //     std::cerr << a[i] << ' ';
    // }

    // std::cerr << '\n';
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        // a[i] = rng() & 1;
        std::cin >> a[i];
    }
}

void print()
{
    assert(ops.size() > 0);
    assert(ops.size() <= 10000);
    std::cout << ops.size() << '\n';
    for (const auto &[x, y] : ops)
    {
        std::cout << x << ' ' << y << '\n';
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

Compilation message

joiris.cpp: In function 'void solve()':
joiris.cpp:179:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  179 |         while (ops.size() > time_to_add)
      |                ~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 424 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 600 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 452 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Incorrect 0 ms 348 KB Output isn't correct
36 Halted 0 ms 0 KB -