oj.uz

Submission #150873

# Submission time Handle Problem Language Result Execution time Memory
150873 2019-09-01T09:50:53 Z cheetose Brunhilda’s Birthday (BOI13_brunhilda) C++11
77.4603 / 100
 416 ms 118524 KB 
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#include<string>
#include<stack>
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>
#include<cstring>
#include<complex>
#include<cmath>
#include<iomanip>
#include<numeric>
#include<algorithm>
#include<list>
#include<functional>
#include<cassert>
#define mp make_pair
#define pb push_back
#define X first
#define Y second
#define y0 y12
#define y1 y22
#define INF 987654321
#define PI 3.141592653589793238462643383279502884
#define fup(i,a,b,c) for(int (i)=(a);(i)<=(b);(i)+=(c))
#define fdn(i,a,b,c) for(int (i)=(a);(i)>=(b);(i)-=(c))
#define MEM0(a) memset((a),0,sizeof(a));
#define MEM_1(a) memset((a),-1,sizeof(a));
#define ALL(a) a.begin(),a.end()
#define SYNC ios_base::sync_with_stdio(false);cin.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> Pi;
typedef pair<ll, ll> Pll;
typedef pair<ld, ld> Pd;
typedef vector<int> Vi;
typedef vector<ll> Vll;
typedef vector<double> Vd;
typedef vector<Pi> VPi;
typedef vector<Pll> VPll;
typedef vector<Pd> VPd;
typedef tuple<int, int, int> iii;
typedef tuple<int,int,int,int> iiii;
typedef tuple<ll, ll, ll> LLL;
typedef vector<iii> Viii;
typedef vector<LLL> VLLL;
typedef complex<double> base;
const ll MOD = 1000000007;
ll POW(ll a, ll b, ll MMM = MOD) {ll ret=1; for(;b;b>>=1,a=(a*a)%MMM)if(b&1)ret=(ret*a)% MMM; return ret; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { if (a == 0 || b == 0)return a + b; return a*(b / gcd(a, b)); }
int dx[] = { 0,1,0,-1,1,1,-1,-1 }, dy[] = { 1,0,-1,0,1,-1,1,-1 };

int d[10000003],mx[10000003],to[10000003];
int a[100000];
int main() {
	int n,q;
	scanf("%d%d",&n,&q);
	fup(i,0,n-1,1)scanf("%d",a+i);
	fup(i,0,n-1,1)
	{
		fup(j,a[i],10000001,a[i])mx[j]=a[i];
	}
	int mn=10000000;
	fdn(i,10000000,1,1)
	{
		mn=min(mn,i+1-mx[i+1]);
		to[i]=mn;
	}
	fup(i,1,10000000,1)
	{
		if(to[i]==i)d[i]=INF;
		else d[i]=d[to[i]]+1;
	}
	while(q--)
	{
		int x;
		scanf("%d",&x);
		int ans=d[x];
		if(ans>=INF)puts("oo");
		else printf("%d\n",ans);
	}
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
  ~~~~~^~~~~~~~~~~~~~
brunhilda.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fup(i,0,n-1,1)scanf("%d",a+i);
                ~~~~~^~~~~~~~~~
brunhilda.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
   ~~~~~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 117880 KB Output is correct
2 Correct 144 ms 117748 KB Output is correct
3 Correct 130 ms 117752 KB Output is correct
4 Correct 124 ms 117752 KB Output is correct
5 Correct 138 ms 117676 KB Output is correct
6 Correct 121 ms 117752 KB Output is correct
7 Correct 132 ms 117748 KB Output is correct
8 Correct 137 ms 117724 KB Output is correct
9 Correct 157 ms 117752 KB Output is correct
10 Correct 179 ms 117752 KB Output is correct
11 Correct 173 ms 117756 KB Output is correct
12 Correct 117 ms 117752 KB Output is correct
13 Correct 295 ms 117744 KB Output is correct
14 Correct 315 ms 117948 KB Output is correct
15 Correct 166 ms 117880 KB Output is correct
16 Correct 144 ms 117756 KB Output is correct
17 Correct 150 ms 117852 KB Output is correct
18 Correct 121 ms 117880 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 117880 KB Output is correct
2 Correct 154 ms 118392 KB Output is correct
3 Correct 369 ms 118380 KB Output is correct
4 Correct 162 ms 117792 KB Output is correct
5 Correct 255 ms 118392 KB Output is correct
6 Correct 144 ms 117752 KB Output is correct
7 Correct 140 ms 117880 KB Output is correct
8 Correct 165 ms 117880 KB Output is correct
9 Correct 305 ms 118376 KB Output is correct
10 Correct 375 ms 118368 KB Output is correct
11 Incorrect 366 ms 118268 KB Output isn't correct
12 Correct 208 ms 117756 KB Output is correct
13 Correct 127 ms 117880 KB Output is correct
14 Correct 167 ms 117740 KB Output is correct
15 Correct 297 ms 118156 KB Output is correct
16 Correct 155 ms 118456 KB Output is correct
17 Correct 305 ms 117752 KB Output is correct
18 Correct 303 ms 118516 KB Output is correct

Subtask #3
38.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 118520 KB Output is correct
2 Correct 372 ms 118484 KB Output is correct
3 Correct 380 ms 118524 KB Output is correct
4 Incorrect 243 ms 118496 KB Output isn't correct
5 Incorrect 197 ms 118364 KB Output isn't correct
6 Correct 358 ms 117992 KB Output is correct
7 Correct 287 ms 118240 KB Output is correct
8 Correct 301 ms 118008 KB Output is correct
9 Correct 330 ms 118052 KB Output is correct
10 Correct 250 ms 117752 KB Output is correct
11 Incorrect 218 ms 117752 KB Output isn't correct
12 Correct 289 ms 117864 KB Output is correct
13 Correct 368 ms 118180 KB Output is correct
14 Correct 224 ms 118344 KB Output is correct
15 Incorrect 324 ms 117980 KB Output isn't correct
16 Correct 335 ms 117752 KB Output is correct
17 Correct 302 ms 117892 KB Output is correct
18 Correct 377 ms 118008 KB Output is correct
19 Incorrect 141 ms 117752 KB Output isn't correct
20 Correct 389 ms 118032 KB Output is correct
21 Incorrect 255 ms 118352 KB Output isn't correct
22 Correct 407 ms 118360 KB Output is correct
23 Correct 200 ms 118008 KB Output is correct
24 Correct 169 ms 118008 KB Output is correct
25 Incorrect 273 ms 118264 KB Output isn't correct
26 Incorrect 255 ms 118136 KB Output isn't correct
27 Correct 416 ms 118264 KB Output is correct
28 Incorrect 164 ms 117960 KB Output isn't correct
29 Correct 385 ms 118296 KB Output is correct
30 Correct 347 ms 118264 KB Output is correct
31 Correct 195 ms 118008 KB Output is correct
32 Incorrect 206 ms 117956 KB Output isn't correct
33 Incorrect 182 ms 118008 KB Output isn't correct
34 Correct 282 ms 118232 KB Output is correct
35 Incorrect 176 ms 118008 KB Output isn't correct
36 Correct 379 ms 118212 KB Output is correct
37 Incorrect 198 ms 118364 KB Output isn't correct
38 Correct 339 ms 118100 KB Output is correct
39 Incorrect 180 ms 118096 KB Output isn't correct
40 Correct 286 ms 118036 KB Output is correct
41 Correct 253 ms 118264 KB Output is correct
42 Incorrect 355 ms 118112 KB Output isn't correct