| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 487500 |
2021-11-15T17:05:12 Z |
inksamurai |
Tenis (COCI20_tenis) |
C++17 |
|
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;
| ^~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
