Submission #523852

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523852	2022-02-08T09:34:00 Z	tato	Spiderman (COCI20_spiderman)	C++14	56 / 70	1220 ms	14408 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];
			}
	
	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:78:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |  for(int i = 0; i < v.size(); i++)
      |                 ~~^~~~~~~~~~
spiderman.cpp:86:6: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
   86 |    if(v[i] > k)
      |      ^
spiderman.cpp:93:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |  for(int i = 0; i < pas.size(); i++)
      |                 ~~^~~~~~~~~~~~
spiderman.cpp:73:12: warning: iteration 1000000 invokes undefined behavior [-Waggressive-loop-optimizations]
   73 |   if(used[i] != 0)
      |      ~~~~~~^
spiderman.cpp:72:19: note: within this loop
   72 |  for(int i = 1; i <= 1000001; i++)
      |                 ~~^~~~~~~~~~

Subtask #1

56.0 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	4880 KB	Output is correct
2	Correct	10 ms	3104 KB	Output is correct
3	Correct	358 ms	6736 KB	Output is correct
4	Correct	930 ms	10964 KB	Output is correct
5	Incorrect	376 ms	9876 KB	Output isn't correct
6	Incorrect	1026 ms	14256 KB	Output isn't correct
7	Correct	403 ms	10076 KB	Output is correct
8	Correct	393 ms	9880 KB	Output is correct
9	Correct	1220 ms	14352 KB	Output is correct
10	Correct	1168 ms	14408 KB	Output is correct