Submission #1079381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079381		boris_mihov	JOIRIS (JOI16_joiris)	C++17	15 / 100	1 ms	348 KiB

joiris

#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();
        for (int i = 1 ; i <= 400 ; ++i)
        {
            ops.push_back({1, n});
            a[n] += 2;
        }

        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++; times++;
        times -= a[n];
        assert(times % 2 == 0);
        times /= 2;
        std::vector <std::pair <int,int>> popped;
        while (ops.size() > time_to_add)
        {
            popped.push_back(ops.back());
            ops.pop_back();
        }

        for (int i = 0 ; i < times ; ++i)
        {
            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 (stderr)

joiris.cpp: In function 'void solve()':
joiris.cpp:178: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]
  178 |         while (ops.size() > time_to_add)
      |                ~~~~~~~~~~~^~~~~~~~~~~~~
joiris.cpp:178:29: warning: 'time_to_add' may be used uninitialized in this function [-Wmaybe-uninitialized]
  178 |         while (ops.size() > time_to_add)
      |                             ^~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 15 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 55