oj.uz

Submission #234998

# Submission time Handle Problem Language Result Execution time Memory
234998 2020-05-26T15:29:24 Z Pajaraja 별자리 2 (JOI14_constellation2) C++17
100 / 100
 1060 ms 692 KB 
#include <bits/stdc++.h>
#define MAXN 3007
using namespace std;
struct point {
    long long x,y;
    int ind,c;
};
long long cnn[3],cnp[3];
int n;
point a[MAXN];
vector<pair<point,bool>> u;
long long orient(point p,point q,point r) 
{
    return (q.x-p.x)*(r.y-p.y)-(q.y-p.y)*(r.x-p.x);
}
bool operator <(point p,point q) 
{
    return orient(p,q,a[0])>0;
}
int main()
{
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%lld%lld%d",&a[i].x,&a[i].y,&a[i].c);
		a[i].ind=i;
	}
	long long res=0;
	for(int i=0;i<n;i++)
	{
		swap(a[i],a[0]);
		u.clear();
		for(int j=1;j<n;j++)
		{
			if(a[j].x>=a[0].x) u.push_back({a[j],true});
			else 
			{
				point f; f.x=2*a[0].x-a[j].x; f.y=2*a[0].y-a[j].y; f.ind=a[i].ind; f.c=a[j].c;
				u.push_back({f,false});
			}
		}
		sort(u.begin(),u.end());
		for(int j=0;j<3;j++) cnp[j]=cnn[j]=0;
		for(int j=0;j<u.size();j++)
		{
			if(u[j].second) cnp[u[j].first.c]++;
			else cnn[u[j].first.c]++;
		}
		for(int j=0;j<u.size();j++)
		{
			if(u[j].second) cnp[u[j].first.c]--;
			else cnn[u[j].first.c]--;
			long long t1=1,t2=1,t3=1,t4=1;
			for(int z=0;z<3;z++) if(a[0].c!=z) t1*=cnp[z];
			for(int z=0;z<3;z++) if(a[0].c!=z) t2*=cnn[z];
			for(int z=0;z<3;z++) if(u[j].first.c!=z) t3*=cnp[z];
			for(int z=0;z<3;z++) if(u[j].first.c!=z) t4*=cnn[z];
			res+=(t1*t4+t2*t3);
			if(!u[j].second) cnp[u[j].first.c]++;
			else cnn[u[j].first.c]++;
		}
	}
	//assert(res%4==0);
	res=res/4LL;
	printf("%lld",res);
}

Compilation message

constellation2.cpp: In function 'int main()':
constellation2.cpp:44:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<u.size();j++)
               ~^~~~~~~~~
constellation2.cpp:49:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<u.size();j++)
               ~^~~~~~~~~
constellation2.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
constellation2.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%d",&a[i].x,&a[i].y,&a[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 7 ms 384 KB Output is correct
5 Correct 8 ms 384 KB Output is correct
6 Correct 14 ms 384 KB Output is correct
7 Correct 13 ms 384 KB Output is correct
8 Correct 13 ms 404 KB Output is correct
9 Correct 13 ms 384 KB Output is correct
10 Correct 11 ms 384 KB Output is correct
11 Correct 14 ms 384 KB Output is correct
12 Correct 13 ms 384 KB Output is correct

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 384 KB Output is correct
2 Correct 86 ms 384 KB Output is correct
3 Correct 109 ms 384 KB Output is correct
4 Correct 111 ms 464 KB Output is correct
5 Correct 248 ms 512 KB Output is correct
6 Correct 432 ms 632 KB Output is correct
7 Correct 728 ms 640 KB Output is correct
8 Correct 1020 ms 692 KB Output is correct
9 Correct 1060 ms 664 KB Output is correct
10 Correct 1046 ms 640 KB Output is correct
11 Correct 1043 ms 692 KB Output is correct
12 Correct 1004 ms 692 KB Output is correct
13 Correct 1034 ms 692 KB Output is correct
14 Correct 1040 ms 692 KB Output is correct
15 Correct 1057 ms 640 KB Output is correct
16 Correct 1000 ms 640 KB Output is correct