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
#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++)
      |                 ~~^~~~~~~~~~
# 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