Submission #243399

#	Time	Username	Problem	Language	Result	Execution time	Memory
243399		Lawliet	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	0 / 100	288 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];

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 = v[i] ; cur < MAXN ; 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 = MAXN - 1 ; i > 0 ; i--)
	{
		dp[i] = mn;

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

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

	for(int i = 1 ; i < MAXN ; i++)
	{
		if( dp[i] == i ) dp[i] = INF;
		else dp[i] = dp[ dp[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:19: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:22:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[i]);
   ~~~~~^~~~~~~~~~~~
brunhilda.cpp:60: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