oj.uz

Submission #251815

# Submission time Handle Problem Language Result Execution time Memory
251815 2020-07-22T10:35:12 Z leaked Izbori (COCI17_izbori) C++14
36 / 80
 31 ms 512 KB 
#include<bits/stdc++.h>
using namespace std;
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//
//    #pragma GCC optimize("unroll-loops")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")
//#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fi first
#define f first
#define se second
#define s second
#define vi_a vector<int>a;
#define p_b push_back
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ll long long
typedef unsigned long long ull;
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(),x.end()
#define getfiles    ifstream cin("input.txt");ofstream cout("output.txt");
#define pw(x) (1ll << x)
#define sz(x) (int)x.size()
#define endl "\n"
#define rall(x) x.rbegin(),x.rend()
#define len(a) (ll)a.size()
#define rep(x,l,r) for(ll x=l;x<r;x++)

//using namespace __gnu_pbds;
ld eps = (ld)1 / 1e6;
const ld pi=3.14159265359;
ll inf = 1e18,mod1=1e9+7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const ll R=1e4;
const ll tx[4]={0,0,-1,1};
const ll ty[4]={-1,1,0,0};
const char rev_to[4]={'E','W','N','S'};
const int N=1e6+1e5;
const int M=1e9+7;
//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> st;
auto rnd=bind(uniform_int_distribution<ll>(1,1e18),mt19937(time(0)));
bool used[N];
signed main()
{
    fast_io;
    int n,m,k;
    cin>>n>>m>>k;--k;
    vector<int>pos(n,0);
    vector<set<int>>lol(m);
    vector<vector<int>>a(n,vector<int>(m));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>a[i][j];a[i][j]--;
        }
        lol[a[i][0]].insert(i);
    }
    set<pii>who;
    for(int i=0;i<m;i++){
        who.insert({sz(lol[i]),-i});
    }
    cout<<-who.rbegin()->s+1<<endl;
    int ans=2e9;
    for(int mask=0;mask<pw(m);mask++){
        if(!(pw(k) & mask)) continue;
        vector<pii>wh;
        vector<int>cnt(n,0);
        for(int i=0;i<n;i++){
            int j=0;
            while(!(pw(a[i][j]) & mask)) j++;
            cnt[a[i][j]]++;
        }
        for(int i=0;i<m;i++){
            wh.p_b({cnt[i],-i});
        }
        sort(rall(wh));
        if(wh[m-1].s==-k) ans=min(ans,m-__builtin_popcount(mask));
    }
    cout<<ans;
    return 0;
}
/*
01011
/
11100
/
11011
/
10110
/
*/

Subtask #1
36.0 / 80.0

# Verdict Execution time Memory Grader output
1 Partially correct 2 ms 384 KB Partially correct
2 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Partially correct 1 ms 384 KB Partially correct
4 Partially correct 7 ms 384 KB Partially correct
5 Partially correct 3 ms 384 KB Partially correct
6 Partially correct 2 ms 384 KB Partially correct
7 Partially correct 1 ms 384 KB Partially correct
8 Runtime error 1 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Partially correct 4 ms 384 KB Partially correct
10 Partially correct 1 ms 384 KB Partially correct
11 Partially correct 4 ms 384 KB Partially correct
12 Partially correct 14 ms 384 KB Partially correct
13 Partially correct 27 ms 384 KB Partially correct
14 Partially correct 15 ms 384 KB Partially correct
15 Partially correct 4 ms 384 KB Partially correct
16 Partially correct 31 ms 384 KB Partially correct
17 Partially correct 14 ms 384 KB Partially correct
18 Partially correct 30 ms 384 KB Partially correct
19 Partially correct 30 ms 384 KB Partially correct
20 Partially correct 31 ms 384 KB Partially correct