oj.uz

Submission #617335

# Submission time Handle Problem Language Result Execution time Memory
617335 2022-08-01T10:52:07 Z errorgorn 별자리 2 (JOI14_constellation2) C++17
100 / 100
 1310 ms 552 KB 
#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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

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

Subtask #3
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 340 KB Output is correct
2 Correct 106 ms 392 KB Output is correct
3 Correct 143 ms 392 KB Output is correct
4 Correct 134 ms 348 KB Output is correct
5 Correct 314 ms 440 KB Output is correct
6 Correct 521 ms 468 KB Output is correct
7 Correct 887 ms 532 KB Output is correct
8 Correct 1259 ms 544 KB Output is correct
9 Correct 1268 ms 552 KB Output is correct
10 Correct 1209 ms 532 KB Output is correct
11 Correct 1310 ms 540 KB Output is correct
12 Correct 1255 ms 544 KB Output is correct
13 Correct 1250 ms 544 KB Output is correct
14 Correct 1309 ms 544 KB Output is correct
15 Correct 1270 ms 540 KB Output is correct
16 Correct 1210 ms 548 KB Output is correct