oj.uz

Submission #1088467

# Submission time Handle Problem Language Result Execution time Memory
1088467 2024-09-14T12:57:50 Z HishamAlshehri Izbori (COCI17_izbori) C++17
80 / 80
 11 ms 464 KB 
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define int long long
#define mod 1000000007
#define base 7001
#define base2 757
// #define pi acos(-1)
#define double long double
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag,tree_order_statistics_node_update>

#pragma GCC optimize("O3,Ofast,unroll-loops")
#pragma GCC target("avx2,sse3,sse4,avx")

constexpr int maxn = 1000001;
const int N = 1 << (int)(ceil(log2(maxn)));

int n, m, k;
int a[101][16], mn = 20;
bool take[16];

void f(int i, int cnt) {
    if (i > m) {
        short frq[16] = {};
        for (int j = 0; j < n; j++) {
            for (int c = 0; c <= cnt; c++){
                if (!take[a[j][c]]) {
                    frq[a[j][c]]++; 
                    break;
                }
            }
        }
        short mx = 0, mxi = 1;
        for (int j = 1; j <= m; j++)
        {
            if (frq[j] > mx)
            {
                mx = frq[j];
                mxi = j;
            }
        }
        if (mxi == k)
        {
            // int ans = 0;
            // for (int j = 0; j < 16; j++) {
            //     if (take[j]) ans++;
            // }
            mn = min(mn, cnt);
        }
        return;
    }
    if (i != k) {
        take[i] = 1;
        f(i + 1, cnt + 1);
        take[i] = 0;
    }
    f(i + 1, cnt);
    return;
}

signed main() 
{
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m >> k;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];
    int frq[16] = {};
    for (int i = 0; i < n; i++) frq[a[i][0]]++;
    short mx = 1, mxi = 1;
    for (int j = 1; j <= m; j++)
    {
        if (frq[j] > mx)
        {
            mx = frq[j];
            mxi = j;
        }
    }
    cout << mxi << "\n";
    f(1, 0);
    cout << mn;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 4 ms 344 KB Output is correct
13 Correct 9 ms 464 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 2 ms 344 KB Output is correct
16 Correct 10 ms 348 KB Output is correct
17 Correct 5 ms 464 KB Output is correct
18 Correct 9 ms 464 KB Output is correct
19 Correct 10 ms 348 KB Output is correct
20 Correct 11 ms 348 KB Output is correct