Submission #481543

#TimeUsernameProblemLanguageResultExecution timeMemory
481543CSQ31Tenis (COCI20_tenis)C++17
110 / 110
113 ms8820 KiB
#pragma GCC optimize("Ofast") #include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define sz(a) (int)(a.size()) #define all(a) a.begin(),a.end() #define lb lower_bound #define ub upper_bound #define owo ios_base::sync_with_stdio(0);cin.tie(0); #define MOD (ll)(998244353) #define INF (ll)(1e18) #define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr) #define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\ debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC)) typedef long long int ll; typedef long double ld; typedef pair<ll,ll> PII; typedef pair<int,int> pii; typedef vector<vector<int>> vii; typedef vector<vector<ll>> VII; ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);} const int MAXN = 1e5+1; int a[3][MAXN],ans[MAXN],w[MAXN],mask[MAXN],f[8]; ll cr[3]; vii pmask(100),tmask(100),same(MAXN); //if 1-1 exist,we fine just take first 1,1 //only case we need to worry about is 2 bits + its complement //this case we need info on the two zeros in the complement //we need an extra mask for each mask with two zero int main() { owo int n; cin>>n; for(int j=0;j<3;j++){ for(int i=0;i<n;i++){ int c; cin>>c; a[j][c-1]=i; } } for(int i=0;i<n;i++){ w[i] = min({a[0][i],a[1][i],a[2][i]}); int d0=-1,d1=-1; for(int j=0;j<3;j++){ if(w[i] == a[j][i]){ mask[i]+=(1<<j); }else{ if(d0==-1)d0=j; else d1=j; } } pmask[mask[i]].pb(w[i]); if(__builtin_popcount(mask[i]) == 1){ if(a[d0][i] <= a[d1][i])tmask[mask[i]].pb(w[i]); else tmask[mask[i]+8].pb(w[i]); //two zero case,annoying } same[w[i]].pb(i); } for(int i=0;i<8;i++){ for(int j=0;j<3;j++)if(i&(1<<j)){f[i]=j;break;} //first bit on } for(int i=0;i<20;i++){ sort(all(pmask[i])); sort(all(tmask[i])); } for(int i=0;i<n;i++){ vector<int>d; for(int j=0;j<3;j++)if(mask[i] &(1<<j))d.pb(j); for(int j=0;j<8;j++){ int res = sz(pmask[j]) - (ub(all(pmask[j]),w[i]) - pmask[j].begin()); ans[i]+=res; if(sz(d) == 1)cr[d[0]]+=res; //only bit else if(sz(d) == 3)cr[f[j]]+=res; //take first bit else{ if(mask[i]&j){ if(j & (1<<d[0]))cr[d[0]]+=res; else cr[d[1]]+=res; } else{ cr[d[0]]+=sz(tmask[j]) - (ub(all(tmask[j]),w[i]) - tmask[j].begin()); cr[d[1]]+=sz(tmask[j+8]) - (ub(all(tmask[j+8]),w[i]) - tmask[j+8].begin()); } } } } //non strict wins for(int i=0;i<n;i++){ //this should be correct for(int j=0;j<sz(same[i]);j++){ for(int k=j+1;k<sz(same[i]);k++){ int v = same[i][j]; int u = same[i][k]; int wv = a[0][v],wu = a[0][u],id = 0; for(int l=1;l<3;l++){ if(min(a[l][v],a[l][u])<min(wv,wu)){ id = l; wv = a[l][v]; wu = a[l][u]; }else if(min(a[l][v],a[l][u]) == min(wv,wu)){ if(max(a[l][v],a[l][u]) < max(wv,wu)){ id = l; wv = a[l][v]; wu = a[l][u]; } } } cr[id]++; if(wv < wu)ans[v]++; else ans[u]++; } } } cout<<cr[0]<<" "<<cr[1]<<" "<<cr[2]<<'\n'; for(int i=0;i<n;i++)cout<<ans[i]<<" "; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...