Submission #1138041

#TimeUsernameProblemLanguageResultExecution timeMemory
1138041_rain_Tenis (COCI20_tenis)C++20
80 / 110
44 ms8516 KiB
// Source: https://usaco.guide/general/io

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

typedef long long LL;

#define FOR(i,a,b) for(int i=1;i<=n;++i)
#define FORD(i,a,b) for(int i=n;i>=1;--i)

const int mxx=3;
const int N=1e5;
vector<int>block[N+2];
int n;
int a[N+2][mxx+2];
int win[N+2],cnt[4]={};
int streak_2[4][4],streak_3[4];

int Get_mn(int id){
	return min({a[id][1],a[id][2],a[id][3]});
}
void same_compo(int i,int j,int gt){
	int true_id=1,ogc=n+1;
	for(int id=1;id<=3;++id){
			if (min(a[i][id],a[j][id])==gt){
				if (ogc>max(a[i][id],a[j][id])) {
					ogc=max(a[i][id],a[j][id]);
					true_id=id;
				}
			}
	}
	cnt[true_id]++;
	for(int id=1;id<=3;++id){
		if (id==true_id) {
			if (a[i][id]>a[j][id]) win[j]++; else win[i]++;
		}
	}
	return;
}

int main(){
		ios::sync_with_stdio(false);
		cin.tie(0); cout.tie(0);

		cin>>n;
		int total=0;
		for(int i=1;i<=mxx;++i){
			for(int j=1;j<=n;++j){
				int t; cin>>t;
				a[t][i]=j;
			}
		}
		for(int i=1;i<=n;++i) block[Get_mn(i)].push_back(i);
		for(int i=n;i>=1;--i){
				for(int id1=0;id1<(int)block[i].size();++id1){
					for(int id2=id1+1;id2<(int)block[i].size();++id2){
							same_compo(block[i][id1],block[i][id2],i);
					}
				}
				for(auto&x:block[i]){
					win[x]+=total;
					//.... CHECKING WIN - STREAK 
						vector<int>pos;
						for(int id=1;id<=3;++id){
								if (a[x][id]==Get_mn(x)) pos.push_back(id);
						}

						if (pos.size()==1) cnt[pos[0]]+=total; 
						if (pos.size()==2) cnt[pos[0]]+=streak_2[pos[0]][pos[1]],cnt[pos[1]]+=streak_2[pos[1]][pos[0]];
						if (pos.size()==3) {
							for(int id=1;id<=3;++id) cnt[id]+=streak_3[id];
						}
						
				}
				//... PRE-PROCESSING THE DATA FOR WIN STREAK 2 AND WIN STREAK 3
					for(auto&x:block[i]){
							int true_id=0,ogc=n+1;
							for(int id=1;id<=3;++id){
									if (ogc>a[x][id]) ogc=a[x][id],true_id=id;
									for(int oid=id;oid<=3;++oid){
										if (a[x][id]==a[x][oid]) streak_2[min(id,oid)][max(id,oid)]++;
										if (a[x][id]>a[x][oid]) streak_2[oid][id]++; 
										if (a[x][id]<a[x][oid]) streak_2[id][oid]++;
									}
							}
							streak_3[true_id]++;
					}
					total+=(int)block[i].size();

				//... DEBUG PROGRESS
					// printf("(DEBUG)\n");
					// printf("-BLOCK- %d %d\n",i,(int)block[i].size());
					// 	for(auto&x:block[i]) printf("%d ",x); printf("\n");
					// printf("(END-DEBUG)\n");
		}
		cout<<cnt[1]<<' '<<cnt[2]<<' '<<cnt[3]<<'\n';
		for(int i=1;i<=n;++i) cout<<win[i]<<" \n"[i==n];
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...