oj.uz

Submission #158205

# Submission time Handle Problem Language Result Execution time Memory
158205 2019-10-15T13:32:46 Z Lawliet Brunhilda’s Birthday (BOI13_brunhilda) C++14
0 / 100
 359 ms 262148 KB 
#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];

bool isMultiple[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

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:45:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j = 0 ; j < d[ i ].size() ; j++)
                   ~~^~~~~~~~~~~~~~~
brunhilda.cpp:22: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:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[i]);
   ~~~~~^~~~~~~~~~~~
brunhilda.cpp:63: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.0

# Verdict Execution time Memory Grader output
1 Runtime error 266 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 241 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 263 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 344 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 269 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 240 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 269 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 329 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 242 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 277 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 247 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 244 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 286 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 337 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 344 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 302 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 359 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 265 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 253 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 245 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 249 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 247 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 298 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 239 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 246 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 246 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 245 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 236 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 343 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 237 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 281 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 248 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 257 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 259 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 249 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 245 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 236 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 237 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 248 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 246 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 255 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 334 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 282 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 239 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 250 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 263 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 276 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 308 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 253 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 290 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 299 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 248 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 257 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 350 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 242 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 290 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 248 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 264 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)