Submission #158207

#	Time	Username	Problem	Language	Result	Execution time	Memory
158207		Lawliet	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	0 / 100	369 ms	262148 KiB

brunhilda

#include <bits/stdc++.h>

using namespace std;

const int MAXM = 100010;
const int MAXN = 10000010;
const int INF = 1000000010;

int m, q;

int v[MAXM];
int dp[MAXN];
int opt[MAXN];

vector< int > d[MAXN];
vector< int > multiples[MAXM];

int main()
{
	scanf("%d %d",&m,&q);

	for(int i = 1 ; i <= m ; i++)
		scanf("%d",&v[i]);

	for(int i = 1 ; i <= m ; i++)
	{
		for(int cur = 0 ; cur < 10000000 ; cur += v[i])
		{
			d[ cur ].push_back( i );
			multiples[ i ].push_back( cur );
		}
	}

	int mn = INF;

	for(int i = 1 ; i <= m ; i++)
		mn = min(mn , 10000000 - (10000000%v[i]));

	for(int i = 10000000 ; i > 0 ; i--)
	{
		opt[ i ] = mn;

		for(int j = 0 ; j < d[ i ].size() ; j++)
		{
			int curPrime = d[ i ][ j ];

			multiples[ curPrime ].pop_back();
			mn = min(mn , multiples[ curPrime ].back());
		}
	}

	for(int i = 1 ; i <= 10000000 ; i++)
	{
		dp[ i ] = INF;
		dp[ i ] = dp[ opt[i] ] + 1;
	}

	for(int i = 1 ; i <= q ; i++)
	{
		int p;
		scanf("%d",&p);

		if(dp[ p ] >= INF) printf("oo\n");
		else printf("%d\n",dp[ p ]);
	}
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < d[ i ].size() ; j++)
                   ~~^~~~~~~~~~~~~~~
brunhilda.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&m,&q);
  ~~~~~^~~~~~~~~~~~~~~
brunhilda.cpp:23:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[i]);
   ~~~~~^~~~~~~~~~~~
brunhilda.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
   ~~~~~^~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60