Submission #523856

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523856	2022-02-08T09:38:10 Z	tato	Spiderman (COCI20_spiderman)	C++14	70 / 70	1150 ms	12480 KB

spiderman

#include <bits/stdc++.h>
#define ll long long
#define pb push_back


using namespace std;

int used[1000001];
int tanr[1000001];

int check(int a, int k)
{
	int b = a -  k;
	int c = sqrt(b);
	
	if(b == 1)
		if(k == 0)
			if(used[1] > 1)
				return used[1] - 1;
			else
				return 0;
		else
			return 0;
	int cnt = 0;
	for(int i = 1; i < c; i++)
		{
			if(b % i == 0)
				{
					if(i > k)
						cnt += used[i];
					
					int d = b / i;
					
					if (d > k)
						cnt += used[d];
						
				}
		}	
	
	if(c*c == b)
		{
			if(c > k)
			cnt += used[c];
		}	
	else
		if(b % c == 0)
			{
				if(c > k)
						cnt += used[c];
					
					int d = b / c;
					
					if (d > k)
						cnt += used[d];
			}
	if(k == 0)
	return cnt - 1;
	else
	return cnt;
	
}
void answer()
{
	int n,x,k,cnt = 0;
	vector < int > v,pas;
	cin >> n >> k;
	
	for(int i = 1; i <= n; i++)
		{
			cin >> x;
			used[x]++;
			v.pb(x);
		}
	for(int i = 1; i <= 1000001; i++)
		if(used[i] != 0)
			{
				cnt += used[i];
				tanr[i] = n - cnt;
			}
	for(int i = 0; i < v.size(); i++)
		{
			if(v[i] < k)
				pas.pb(0);
			
			if(v[i] == k)
				pas.pb(tanr[v[i]]);
				
			if(v[i] > k)
				if((v[i] - k) <= k)
					pas.pb(0);
				else
					pas.pb(check(v[i],k));
		}
		
	for(int i = 0; i < pas.size(); i++)
		cout << pas[i] << ' ';
}

int main()
{
	int t = 1;
	
	//cin >> t;
	
	while(t--)
		answer();
	
	
	
	return 0;
}

Compilation message

spiderman.cpp: In function 'int check(int, int)':
spiderman.cpp:16:4: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   16 |  if(b == 1)
      |    ^
spiderman.cpp: In function 'void answer()':
spiderman.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i = 0; i < v.size(); i++)
      |                 ~~^~~~~~~~~~
spiderman.cpp:88:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   88 |    if(v[i] > k)
      |      ^
spiderman.cpp:95:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |  for(int i = 0; i < pas.size(); i++)
      |                 ~~^~~~~~~~~~~~
spiderman.cpp:75:12: warning: iteration 1000000 invokes undefined behavior [-Waggressive-loop-optimizations]
   75 |   if(used[i] != 0)
      |      ~~~~~~^
spiderman.cpp:74:19: note: within this loop
   74 |  for(int i = 1; i <= 1000001; i++)
      |                 ~~^~~~~~~~~~

Subtask #1

70.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	4812 KB	Output is correct
2	Correct	8 ms	3152 KB	Output is correct
3	Correct	310 ms	6352 KB	Output is correct
4	Correct	882 ms	9160 KB	Output is correct
5	Correct	348 ms	9220 KB	Output is correct
6	Correct	1008 ms	12372 KB	Output is correct
7	Correct	390 ms	9308 KB	Output is correct
8	Correct	386 ms	9272 KB	Output is correct
9	Correct	1150 ms	12280 KB	Output is correct
10	Correct	1141 ms	12480 KB	Output is correct