Submission #617335

#	Time	Username	Problem	Language	Result	Execution time	Memory
617335		errorgorn	별자리 2 (JOI14_constellation2)	C++17	100 / 100	1310 ms	552 KiB

constellation2

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ii pair<int,int>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (int x=(s)-((s)>(e));x!=(e)-((s)>(e));((s)<(e))?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const double TAU=acos(-1)*2;

int n;
ii arr[3005];
int w[3005];

int cnt[2][3];

double diff(double i,double j){
	double res=j-i;
	if (res<0) res+=TAU;
	return res;
}

signed main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n;
	rep(x,0,n) cin>>arr[x].fi>>arr[x].se>>w[x];
	
	int ans=0;
	
	rep(x,0,n){
		#define di pair<double,int>
		vector<di> v;
		rep(y,0,n) if (x!=y){
			v.pub({atan2(arr[y].fi-arr[x].fi,arr[y].se-arr[x].se)+TAU/2,y});
		}
		
		sort(all(v));
		
		//for (auto [a,b]:v) cout<<a<<"_"<<b<<" "; cout<<endl;
		
		memset(cnt,0,sizeof(cnt));
		rep(y,0,n) if (x!=y) cnt[0][w[y]]++;
		
		int idx=0;
		rep(y,0,sz(v)){
			cnt[1][w[v[y].se]]--;
			cnt[0][w[v[y].se]]++;
			
			while (diff(v[y].fi,v[idx].fi)<TAU/2){
				cnt[0][w[v[idx].se]]--;
				cnt[1][w[v[idx].se]]++;
				
				idx=(idx+1)%sz(v);
				if (idx==y) break;
			}
			
			//cout<<x<<" "<<v[y].se<<endl;
			//rep(x,0,3) cout<<cnt[0][x]<<" "; cout<<endl;
			//rep(x,0,3) cout<<cnt[1][x]<<" "; cout<<endl;
			
			int curr=1;
			rep(i,0,3) if (i!=w[v[y].se]) curr*=cnt[0][i];
			rep(i,0,3) if (i!=w[x]) curr*=cnt[1][i];
			ans+=curr;
		}
	}
	
	cout<<ans/2<<endl;
}

• Subtask 1: 15 / 15
• Subtask 2: 40 / 40
• Subtask 3: 45 / 45