Submission #1079376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079376		boris_mihov	JOIRIS (JOI16_joiris)	C++17	15 / 100	1 ms	600 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';

    bool wasEven = (n % 2 == 0);
    // k = 2 from now on
    if (wasEven)
    {
        for (int i = 1 ; i <= 1000 ; ++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++;
        // for (const auto &[t, x] : ops)
        // {
        //     if (t == 1) b[x] += 2;
        //     else
        //     {
        //         b[x]++;
        //         b[x + 1]++;
        //     }
        // }

        // assert(timess )
        // while (b[n] < b[1])
        // {
        //     b[n] += 2;
        //     ops.push_back({1, n});
        // }

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

        times++;
        assert(times <= a[n]);
        while (times < a[n])
        {
            ops.push_back({1, n});
            times += 2;
        }

        assert(times == a[n]);
    }

    // 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;
}

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