Submission #589737

#	Time	Username	Problem	Language	Result	Execution time	Memory
589737		Lam_lai_cuoc_doi	Studentsko (COCI14_studentsko)	C++17	100 / 100	3 ms	2772 KiB

studentsko

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;
constexpr int Inf = 1e9 + 7;

int n, k, a[N], id[N], b[N];
vector<int> p[N];

void Read()
{
    cin >> n >> k;

    for (int i = 1; i <= n; ++i)
        cin >> a[id[i] = i];
}

void Solve()
{
    sort(id + 1, id + n + 1, [&](const int &x, const int &y)
         { return a[x] < a[y]; });

    for (int i = 1; i <= n; ++i)
        b[id[i]] = (i + k - 1) / k;

    fill(a, a + n + 1, Inf);
    a[0] = 0;
    int ans(0);

    for (int i = 1; i <= n; ++i)
    {
        int j = upper_bound(a + 1, a + n + 1, b[i]) - a;

        ans = max(ans, j);
        a[j] = b[i];
    }

    cout << n - ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }

    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case #" << _ << ": ";
        Read();
        Solve();
    }
    // //cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
1
3
1 0 1
1 1 2
0 3 4
 */

Compilation message (stderr)

studentsko.cpp: In function 'void read(T&)':
studentsko.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^
studentsko.cpp: In function 'int32_t main()':
studentsko.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
studentsko.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10