oj.uz

Submission #253418

# Submission time Handle Problem Language Result Execution time Memory
253418 2020-07-28T03:51:19 Z tinjyu Ideal city (IOI12_city) C++14
32 / 100
 226 ms 32384 KB 
#include <iostream>
using namespace std;
long long int sumx[100005],sumy[100005],t[100005],len[100005],n,map[2005][2005],tag[2005][2005];
int DistanceSum(int N, int *x, int *y) {
	n=N;
	int mix=2000000000,miy=2000000000;
	for(int i=0;i<n;i++)
	{
		mix=min(mix,x[i]);
		miy=min(miy,y[i]);
	}
	if(n>2000)
	{
		long long int ans=0;
		for(int i=0;i<n;i++)
		{
			sumx[x[i]]++;
			sumy[y[i]]++;
		}
		long long int now=0,num=0;
		for(int i=0;i<=100000;i++)
		{
			//cout<<sumx[i]<<" "<<now<<" "<<ans<<endl;
			ans+=now*sumx[i];
			num+=sumx[i];
			now+=now+num;
			now%=1000000000;
			ans%=1000000000;
		}
		now=0,num=0;
		for(int i=0;i<=100000;i++)
		{
			ans+=now*sumy[i];
			num+=sumy[i];
			now+=num;
			now%=1000000000;
			ans%=1000000000;
		}
		return ans;
	}
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)map[i][j]=-1;
	}
	for(int i=0;i<n;i++)
	{
		x[i]-=mix;
		y[i]-=miy;
		map[x[i]][y[i]]=i;
	}
	long long int ans=0;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			tag[x[j]][y[j]]=0;
		}
		t[0]=i;
		len[0]=0;
		tag[x[i]][y[i]]=1;
		long long int p=0,pp=0;
		while(p<=pp)
		{
			if(t[p]<i)ans+=len[p];
			ans%=1000000000;
			for(int i=1;i<=4;i++)
			{
				long long int tmpx=x[t[p]],tmpy=y[t[p]];
				if(i==1)tmpx++;
				if(i==2)tmpy++;
				if(i==3)tmpx--;
				if(i==4)tmpy--;
				if(tmpx>=0 && tmpy>=0 && map[tmpx][tmpy]!=-1 && tag[tmpx][tmpy]==0)
				{
					pp++;
					len[pp]=len[p]+1;
					t[pp]=map[tmpx][tmpy];
					tag[tmpx][tmpy]=1;
				}
			}
			p++;		
		}
	}
  return ans;

}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 896 KB Output is correct
5 Correct 1 ms 896 KB Output is correct
6 Correct 3 ms 1536 KB Output is correct
7 Correct 2 ms 1536 KB Output is correct
8 Correct 3 ms 1536 KB Output is correct
9 Correct 2 ms 1536 KB Output is correct
10 Correct 2 ms 1536 KB Output is correct
11 Correct 2 ms 1536 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 12416 KB Output is correct
2 Correct 47 ms 12416 KB Output is correct
3 Correct 133 ms 24320 KB Output is correct
4 Correct 108 ms 24192 KB Output is correct
5 Correct 223 ms 32256 KB Output is correct
6 Correct 154 ms 32128 KB Output is correct
7 Correct 226 ms 32384 KB Output is correct
8 Correct 158 ms 32384 KB Output is correct
9 Correct 150 ms 32128 KB Output is correct
10 Correct 150 ms 32120 KB Output is correct

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -