oj.uz

답안 #487500

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
487500 2021-11-15T17:05:12 Z inksamurai Tenis (COCI20_tenis) C++17
110 / 110
 252 ms 77016 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define sz(a) (ll)a.size()
#define all(a) a.begin(),a.end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define crep(i,x,n) for(ll i=x;i<n;i++)
#define drep(i,n) for(ll i=n-1;i>=0;i--)
#define vec(...) vector<__VA_ARGS__>
#define _322ZVFH ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef long double ld;
using pii=pair<ll,ll>;
using vi=vector<ll>;

int main(){
_322ZVFH;
	ll n;
	cin>>n;
	vec(vi) a(n,vi(3));
	rep(j,3)rep(i,n){
		ll x;
		cin>>x;
		x--;
		a[x][j]=i+1;
	}
	auto gwin=[&](ll i,ll j)->pii{
		ll mna=1e9,mnab=1e9,ca=-1;
		rep(t,3){
			if(a[i][t]<mna){
				mna=a[i][t];
				mnab=a[j][t];
				ca=t;
			}else if(a[i][t]==mna){
				if(a[j][t]<mnab){
					mnab=a[j][t];
					ca=t;
				}
			}
		}
		ll mnb=1e9,mnba=1e9,cb=-1;
		rep(t,3){
			if(a[j][t]<mnb){
				mnb=a[j][t];
				mnba=a[i][t];
				cb=t;
			}else if(a[j][t]==mnb){
				if(a[i][t]<mnba){
					mnba=a[i][t];
					cb=t;
				}
			}
		}
		pii p={-1,-1};
		p=(mna<mnb?pii{mna,mnab}:mnb<mna?pii{mnb,mnba}:mnab<mnba?pii{mna,mnab}:pii{mnb,mnba});
		ll cnt=0,pans1=-1,pans2=-1;
		rep(t,3){
			if(a[i][t]==p.fi and a[j][t]==p.se){
				if(pans1==-1){
					pans1=t;
					pans2=i;
				}
			}
			if(a[j][t]==p.fi and a[i][t]==p.se){
				if(pans2==-1){
					pans1=t;
					pans2=j;
				}
			}
		}
		return {pans1,pans2};
	};
	vec(vec(vec(vi))) psum(n+10,vec(vec(vi))(3,vec(vi)(3,vi(3,0))));
	// val,t,seb/+1,seb/+2
	rep(i,n){
		rep(t,3){
			ll t1=(t+1)%3,t2=(t+2)%3;
			ll cond1=0,cond2=0;
			if(a[i][t]>a[i][t1]) cond1=2;
			else if(a[i][t]<a[i][t1]) cond1=1;
			if(a[i][t]>a[i][t2]) cond2=2;
			else if(a[i][t]<a[i][t2]) cond2=1;
			psum[*min_element(all(a[i]))][t][cond1][cond2]++;
		}
	}
	rep(t,3){
		rep(cond1,3){
			rep(cond2,3){
				drep(i,n+1){
					psum[i][t][cond1][cond2]+=psum[i+1][t][cond1][cond2];
				}
			}
		}
	}
	vi pans(3,0),ppans(n+10,0);
	rep(i,n){
		ll minima=*min_element(all(a[i]));
		ll x=minima,cnt=0;
		rep(t,3) if(a[i][t]==minima) cnt++;
		if(cnt==1){
			rep(t,3){
				if(a[i][t]==minima){
					ll now=0;
					rep(j,3)rep(j1,3){
						now+=psum[x+1][t][j][j1];
					}
					pans[t]+=now;
					ppans[i]+=now;
				}
			}
		}else if(cnt==2){
			ll t0=-1,t1=-1;
			rep(t,3){
				if(a[i][t]==minima){
					if(t0==-1) t0=t;
					else t1=t;
				}
			}
			ll now=0;
			rep(j,3)rep(j1,3){
				if(t1==(t0+1)%3 and j==2) continue;
				if(t1==(t0+2)%3 and j1==2) continue;
				now+=psum[x+1][t0][j][j1];
				// count for t0
			}
			pans[t0]+=now;
			ppans[i]+=now;
			now=0;
			rep(j,3)rep(j1,3){
				if(t0==(t1+1)%3 and j!=1) continue;
				if(t0==(t1+2)%3 and j1!=1) continue;
				now+=psum[x+1][t1][j][j1];
				// count for t1
			}
			pans[t1]+=now;
			ppans[i]+=now;
		}else{
			ll now=0;
			rep(j,3)rep(j1,3){
				if(j==2 or j1==2) continue;
				now+=psum[x+1][0][j][j1];
			}
			pans[0]+=now;
			ppans[i]+=now;
			now=0;
			rep(j,3)rep(j1,3){
				if(j==2 or j1!=1) continue;
				now+=psum[x+1][1][j][j1];
			}
			pans[1]+=now;
			ppans[i]+=now;
			now=0;
			rep(j,3)rep(j1,3){
				if(j!=1 or j1!=1) continue;
				now+=psum[x+1][2][j][j1];
			}
			pans[2]+=now;
			ppans[i]+=now;
		}
	}
	vec(vi) rbts(n+10);
	rep(i,n){
		ll x=*min_element(all(a[i]));
		rbts[x].pb(i);
	}
	set<pii> st;
	crep(minima,1,n+1){
		rep(i,sz(rbts[minima])){
			crep(j,i+1,sz(rbts[minima])){
				ll x=rbts[minima][i],y=rbts[minima][j];
				if(st.find(minmax(x,y))!=st.end()) continue;
				st.insert(minmax(x,y));
				pii p=gwin(x,y);
				pans[p.fi]++;
				ppans[p.se]++;
			}
		}
	}
	// rep(i,n){
	// 	rep(j,n){
	// 		if(i==j or st.find(minmax(i,j))!=st.end()) continue;
	// 		st.insert(minmax(i,j));
	// 		pii p=gwin(i,j);
	// 		pans[p.fi]++;
	// 		ppans[p.se]++;
	// 	}
	// }
	// prll rabbits
	{
		rep(t,3){
			cout<<pans[t]<<" ";
		}
		cout<<"\n";
		rep(i,n){
			cout<<ppans[i]<<" ";
		}
		cout<<"\n";
	}
	// 
//	
	return 0;
}

Compilation message

tenis.cpp: In lambda function:
tenis.cpp:30:23: warning: variable 'ca' set but not used [-Wunused-but-set-variable]
   30 |   ll mna=1e9,mnab=1e9,ca=-1;
      |                       ^~
tenis.cpp:43:23: warning: variable 'cb' set but not used [-Wunused-but-set-variable]
   43 |   ll mnb=1e9,mnba=1e9,cb=-1;
      |                       ^~
tenis.cpp:58:6: warning: unused variable 'cnt' [-Wunused-variable]
   58 |   ll cnt=0,pans1=-1,pans2=-1;
      |      ^~~

Subtask #1
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 460 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 5 ms 2508 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 5 ms 2508 KB Output is correct
5 Correct 90 ms 30952 KB Output is correct
6 Correct 147 ms 46396 KB Output is correct
7 Correct 203 ms 61704 KB Output is correct
8 Correct 252 ms 77016 KB Output is correct
9 Correct 249 ms 76224 KB Output is correct
10 Correct 248 ms 74688 KB Output is correct