oj.uz

Submission #445834

# Submission time Handle Problem Language Result Execution time Memory
445834 2021-07-19T19:52:43 Z Jasiekstrz Tenis (COCI20_tenis) C++17
110 / 110
 114 ms 2764 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N=1e5;
int tab[N+10][3];
int srt[N+10];
long long ans[3];
int win[N+10];
int ww[3][3];
int www[3];
int mn_pos(int x)
{
	return min({tab[x][0],tab[x][1],tab[x][2]});
}
void f(int a,int b)
{
	vector<tuple<int,int,int>> tmp;
	for(int i=0;i<3;i++)
		tmp.emplace_back(min(tab[a][i],tab[b][i]),max(tab[a][i],tab[b][i]),i);
	sort(tmp.begin(),tmp.end());
	int c=get<2>(tmp[0]);
	ans[c]++;
	if(tab[a][c]<tab[b][c])
	{
		win[a]++;
		//cerr<<a<<"\n";
	}
	else
	{
		win[b]++;
		//cerr<<b<<"\n";
	}
	return;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin>>n;
	for(int j=0;j<3;j++)
	{
		for(int i=1;i<=n;i++)
		{
			int x;
			cin>>x;
			tab[x][j]=i;
		}
	}
	for(int i=1;i<=n;i++)
		srt[i]=i;
	sort(srt+1,srt+n+1,[](int a,int b){ return mn_pos(a)>mn_pos(b); });
	for(int i=1;i<=n;i++)
	{
		for(int j=max(1,i-2);j<i;j++)
			f(srt[i],srt[j]);
		if(i-2>0)
		{
			win[srt[i]]+=i-3;
			int mn=mn_pos(srt[i]);
			vector<int> win_pos;
			for(int j=0;j<3;j++)
			{
				if(tab[srt[i]][j]==mn)
					win_pos.push_back(j);
			}
			if(win_pos.size()==1)
				ans[win_pos[0]]+=i-3;
			else if(win_pos.size()==2)
			{
				ans[win_pos[0]]+=ww[win_pos[0]][win_pos[1]];
				ans[win_pos[1]]+=ww[win_pos[1]][win_pos[0]];
			}
			else
			{
				for(int j=0;j<3;j++)
					ans[win_pos[j]]+=www[win_pos[j]];
			}

			vector<pair<int,int>> xd(3);
			for(int j=0;j<3;j++)
				xd[j]={tab[srt[i-2]][j],j};
			sort(xd.begin(),xd.end());
			www[xd[0].se]++;
			int g[3];
			for(int j=0;j<3;j++)
				g[xd[j].se]=j;
			for(int a=0;a<3;a++)
			{
				for(int b=0;b<3;b++)
				{
					if(g[a]<g[b])
						ww[a][b]++;
				}
			}
		}
	}
	cout<<ans[0]<<" "<<ans[1]<<" "<<ans[2]<<"\n";
	for(int i=1;i<=n;i++)
		cout<<win[i]<<" \n"[i==n];
	return 0;
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 3 ms 332 KB Output is correct
5 Correct 41 ms 1300 KB Output is correct
6 Correct 62 ms 1860 KB Output is correct
7 Correct 83 ms 2328 KB Output is correct
8 Correct 106 ms 2764 KB Output is correct
9 Correct 114 ms 2764 KB Output is correct
10 Correct 110 ms 2760 KB Output is correct