oj.uz

Submission #104157

# Submission time Handle Problem Language Result Execution time Memory
104157 2019-04-04T09:02:14 Z Fasho Izbori (COCI17_izbori) C++14
8 / 80
 3000 ms 16128 KB 
#include <bits/stdc++.h>
#define N 1000005
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("myfile.in","r",stdin);freopen ("myfile.out","w",stdout);
#define mod 1000000007
#define fs(x,y) for(int i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(int i=x;i<=y;i++)
using namespace std;

ll n,m,k,ar[105][20],sum,mn=INT_MAX,mark[N],mark2[N],cnt[N];

void f(int ind,int mask)
{
	if(ind>m+1)
		return;
	memset(mark,0,sizeof(mark));
	memset(mark2,0,sizeof(mark2));
	ll tutmac=0;
	for(int i=1;i<=ind;i++)
	{
		int x=(1<<i);
		if(x&mask)
			mark[i]=1,tutmac++;
	}
	int tut=0;

	int x=mask;
	int y=(1<<ind);
	x=mask|y;

	

	ll mki=0;

	for(int i=1;i<=n;i++)
	{
		int tmp=0;
		for(int j=1;j<=m;j++)
		{
			// if(mark[ar[i][j]])
			// 	q++;
			if(!tmp && !mark[ar[i][j]])
			{
				mark2[ar[i][j]]++;
				if(mark2[ar[i][j]]>mark2[mki])
					mki=ar[i][j];
				tmp=1;

			if(mark2[ar[i][j]]==cnt[mki])
				mki=min(mki,ar[i][j]);
			}

		}

		

		}
	// cout<<mask<<sp<<mki<<sp<<k<<sp<<tutmac<<endl;

	if(mki==k)
	{
		mn=min(tutmac,mn);
		return;

	}
	if(mask==0)
	{

		f(ind+1,x);
		f(ind+1,mask);
		return;
	} 
		f(ind+1,x);
		f(ind+1,mask);
}


int main()
{
	fast;
	cin>>n>>m>>k;
	fo(i,1,n)
		fo(j,1,m)
			cin>>ar[i][j];

	ll mkii=0;
	
	fo(i,1,n)
	{
		cnt[ar[i][1]]++;	
		if(cnt[ar[i][1]]>cnt[mkii])
			mkii=ar[i][1];
		if(cnt[ar[i][1]]==cnt[mkii])
			mkii=min(mkii,ar[i][1]);
	}
	cout<<mkii<<endl;

	f(1,0);
	cout<<mn;
}

Compilation message

izbori.cpp: In function 'void f(int, int)':
izbori.cpp:35:6: warning: unused variable 'tut' [-Wunused-variable]
  int tut=0;
      ^~~

Subtask #1
8.0 / 80.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3005 ms 16000 KB Time limit exceeded
2 Execution timed out 3079 ms 16000 KB Time limit exceeded
3 Execution timed out 3015 ms 16000 KB Time limit exceeded
4 Execution timed out 3014 ms 16000 KB Time limit exceeded
5 Execution timed out 3050 ms 16000 KB Time limit exceeded
6 Execution timed out 3097 ms 16000 KB Time limit exceeded
7 Correct 1116 ms 16000 KB Output is correct
8 Execution timed out 3019 ms 15972 KB Time limit exceeded
9 Execution timed out 3040 ms 16000 KB Time limit exceeded
10 Execution timed out 3082 ms 16000 KB Time limit exceeded
11 Correct 16 ms 16128 KB Output is correct
12 Execution timed out 3094 ms 16000 KB Time limit exceeded
13 Execution timed out 3010 ms 16000 KB Time limit exceeded
14 Execution timed out 3025 ms 16008 KB Time limit exceeded
15 Execution timed out 3012 ms 16128 KB Time limit exceeded
16 Execution timed out 3031 ms 16000 KB Time limit exceeded
17 Execution timed out 3089 ms 16000 KB Time limit exceeded
18 Execution timed out 3092 ms 15972 KB Time limit exceeded
19 Execution timed out 3089 ms 16000 KB Time limit exceeded
20 Execution timed out 3049 ms 16000 KB Time limit exceeded