제출 #243404

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243404		Lawliet	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	100 / 100	378 ms	80836 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], mx[MAXN];

int getNext(int value, int p) { return value - value%p; }

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])
			mx[cur] = max( mx[cur] , v[i] );

	int mn = INF;

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

	for(int i = MAXN - 1 ; i > 0 ; i--)
	{
		dp[i] = mn;
		if( mx[i] != 0 ) mn = min( mn , getNext( i - 1 , mx[i] ) );
	}

	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]);
	}
}

컴파일 시 표준 에러 (stderr) 메시지

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:18: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:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[i]);
   ~~~~~^~~~~~~~~~~~
brunhilda.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
   ~~~~~^~~~~~~~~

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