Submission #781874

#	Time	Username	Problem	Language	Result	Execution time	Memory
781874		boris_mihov	Comparing Plants (IOI20_plants)	C++17	14 / 100	4040 ms	9700 KiB

plants

#include "plants.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>

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

int n, k;
int p[MAXN];
int r[MAXN];
bool guessed[MAXN];

int getPrev(int idx)
{
    if (idx == 1) return n;
    return idx - 1;
}

void init(int K, std::vector <int> R) 
{
    k = K;
    n = R.size();
    for (int i = 1 ; i <= n ; ++i)
    {
        r[i] = R[i - 1];
    }

    r[0] = -1;
    for (int currTry = 1 ; currTry <= n ; ++currTry)
    {
        std::vector <int> max;
        for (int i = 1 ; i <= n ; ++i)
        {
            if (guessed[i])
            {
                continue;
            }

            if (r[i] == k - 1)
            {
                max.push_back(i);
            }
        }

        assert(max.size());
        int pos = max[0];
        if (max.back() >= pos + k)
        {
            for (const int &j : max)
            {
                if (pos + k <= j)
                {
                    pos = j;
                    break;
                }
            }
        }

        guessed[pos] = true;
        p[pos] = currTry;
        int idx = getPrev(pos);
        for (int i = 1 ; i < k ; ++i)
        {
            r[idx]++;
            idx = getPrev(idx);
        }
    }

	return;
}

int compare_plants(int x, int y)
{
    x++;
    y++;
	if (p[x] < p[y]) return -1;
    return 1;
}

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25