oj.uz

Submission #589737

# Submission time Handle Problem Language Result Execution time Memory
589737 2022-07-05T08:17:56 Z Lam_lai_cuoc_doi Studentsko (COCI14_studentsko) C++17
100 / 100
 3 ms 2772 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2676 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2672 KB Output is correct
2 Correct 2 ms 2672 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2744 KB Output is correct
2 Correct 3 ms 2696 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2688 KB Output is correct
2 Correct 3 ms 2692 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 3 ms 2772 KB Output is correct