oj.uz

Submission #150870

# Submission time Handle Problem Language Result Execution time Memory
150870 2019-09-01T09:48:30 Z cheetose Brunhilda’s Birthday (BOI13_brunhilda) C++11
75.2381 / 100
 424 ms 120004 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
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 123 ms 117752 KB Output isn't correct
2 Correct 148 ms 117752 KB Output is correct
3 Correct 131 ms 117712 KB Output is correct
4 Correct 124 ms 117804 KB Output is correct
5 Correct 138 ms 117712 KB Output is correct
6 Incorrect 131 ms 117744 KB Output isn't correct
7 Correct 132 ms 117752 KB Output is correct
8 Correct 138 ms 117668 KB Output is correct
9 Correct 158 ms 117708 KB Output is correct
10 Correct 183 ms 117724 KB Output is correct
11 Correct 176 ms 117756 KB Output is correct
12 Correct 119 ms 117848 KB Output is correct
13 Correct 295 ms 117884 KB Output is correct
14 Correct 296 ms 117880 KB Output is correct
15 Correct 160 ms 117680 KB Output is correct
16 Correct 146 ms 117752 KB Output is correct
17 Correct 155 ms 117776 KB Output is correct
18 Correct 124 ms 117764 KB Output is correct

Subtask #2
18.8888888889 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 117844 KB Output is correct
2 Correct 157 ms 118764 KB Output is correct
3 Correct 393 ms 118560 KB Output is correct
4 Correct 176 ms 117752 KB Output is correct
5 Correct 264 ms 118264 KB Output is correct
6 Correct 145 ms 117752 KB Output is correct
7 Correct 140 ms 117880 KB Output is correct
8 Correct 168 ms 117684 KB Output is correct
9 Correct 309 ms 118488 KB Output is correct
10 Correct 379 ms 118408 KB Output is correct
11 Incorrect 369 ms 118132 KB Output isn't correct
12 Correct 214 ms 117880 KB Output is correct
13 Correct 128 ms 117752 KB Output is correct
14 Correct 170 ms 117740 KB Output is correct
15 Correct 300 ms 118152 KB Output is correct
16 Correct 158 ms 118740 KB Output is correct
17 Correct 312 ms 117808 KB Output is correct
18 Correct 307 ms 118832 KB Output is correct

Subtask #3
38.5714285714 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 308 ms 118752 KB Output is correct
2 Correct 381 ms 118776 KB Output is correct
3 Correct 392 ms 118788 KB Output is correct
4 Incorrect 249 ms 118720 KB Output isn't correct
5 Incorrect 242 ms 120004 KB Output isn't correct
6 Correct 364 ms 118788 KB Output is correct
7 Correct 323 ms 119388 KB Output is correct
8 Correct 361 ms 118668 KB Output is correct
9 Correct 305 ms 118644 KB Output is correct
10 Correct 250 ms 117880 KB Output is correct
11 Incorrect 218 ms 118132 KB Output isn't correct
12 Correct 283 ms 117972 KB Output is correct
13 Correct 367 ms 118964 KB Output is correct
14 Correct 220 ms 119084 KB Output is correct
15 Incorrect 296 ms 118088 KB Output isn't correct
16 Correct 345 ms 117980 KB Output is correct
17 Correct 300 ms 118264 KB Output is correct
18 Correct 384 ms 118544 KB Output is correct
19 Incorrect 140 ms 118008 KB Output isn't correct
20 Correct 383 ms 118904 KB Output is correct
21 Incorrect 251 ms 119224 KB Output isn't correct
22 Correct 413 ms 119820 KB Output is correct
23 Correct 234 ms 119092 KB Output is correct
24 Correct 169 ms 118776 KB Output is correct
25 Incorrect 275 ms 118892 KB Output isn't correct
26 Incorrect 296 ms 118704 KB Output isn't correct
27 Correct 424 ms 119400 KB Output is correct
28 Incorrect 165 ms 118776 KB Output isn't correct
29 Correct 387 ms 119760 KB Output is correct
30 Correct 356 ms 119544 KB Output is correct
31 Correct 191 ms 118724 KB Output is correct
32 Incorrect 209 ms 118748 KB Output isn't correct
33 Incorrect 151 ms 118648 KB Output isn't correct
34 Correct 286 ms 119464 KB Output is correct
35 Incorrect 174 ms 118776 KB Output isn't correct
36 Correct 392 ms 119716 KB Output is correct
37 Incorrect 194 ms 119824 KB Output isn't correct
38 Correct 335 ms 118756 KB Output is correct
39 Incorrect 178 ms 118844 KB Output isn't correct
40 Correct 293 ms 118884 KB Output is correct
41 Correct 249 ms 119416 KB Output is correct
42 Incorrect 354 ms 118908 KB Output isn't correct