Submission #480425

#	Time	Username	Problem	Language	Result	Execution time	Memory
480425		lukameladze	Tenis (COCI20_tenis)	C++14	110 / 110	594 ms	86468 KiB

tenis

# include <bits/stdc++.h>
#define f first
#define int long long
#define s second
#define pb push_back
using namespace std;
const int N = 3e5 + 5;
int n, a[4][N],ans[5], idx[N][5],aa,bb,fix[5],cnt[N],bstt[N],vl,id[N],x,y,val;
multiset < int > ms;
vector < pair <int, int > > v;
int ans1[N];
multiset <int > ms1[N];
multiset < int >::iterator it;
map <int, int > fx[N];
void add(int aa, int bb, int j) {
     if (fx[aa][bb]) return ;
     fx[aa][bb] = fx[bb][aa] = 1;
     if (aa == bb) return ;
     int mnid,mnid1,mn,mn1,kk;
     int bestaa = min(idx[aa][1], min(idx[aa][2], idx[aa][3]));
      int bestbb = min(idx[bb][1], min(idx[bb][2], idx[bb][3]));
      if (bestaa == bestbb && bestaa == j) {
           mnid = 1e9;
           mnid1 = 1e9;
           int winner = 0;
           for (int i = 1; i <= 3; i++) {
                mn = min(idx[aa][i],idx[bb][i]); mn1 = max(idx[aa][i],idx[bb][i]);
                if (mn < mnid) {
                	 if (mn == idx[aa][i] && mn1 == idx[bb][i]) winner = aa;
                	 else winner = bb;
                     kk = i;
                     mnid = mn; mnid1 = mn1;
                }
                else if (mn == mnid && mn1 < mnid1) { if (mn == idx[aa][i] && mn1 == idx[bb][i]) winner = aa;
                	 else winner = bb;
                     kk = i;
                     mnid = mn; mnid1 = mn1;
                }
           }ans1[winner] ++;
           ans[kk]++;
      }
}
main() {
     cin>>n;
     for (int i = 1; i <= 3; i++) {
          for (int j = 1; j <= n; j++)
          cin>>a[i][j], idx[a[i][j]][i] = j;
     }for (int j = 1; j <= n; j++) ms.insert(j);
     for (int j = 1; j <= n; j++) {
          aa = a[1][j]; bb = a[2][j];
          add(aa,bb,j);
          aa = a[2][j]; bb = a[3][j];
          add(aa,bb,j);
          aa = a[3][j]; bb = a[1][j];
          add(aa,bb,j);
     }
    
     for (int i = 1; i <= n; i++) {
          bstt[i] = min(idx[i][1],min(idx[i][2],idx[i][3]));
          v.clear();
          v.pb({idx[i][1],1}); v.pb({idx[i][2],2}); v.pb({idx[i][3],3});
          sort(v.begin(),v.end());
          val = 0;
          for (int j = 0 ; j < v.size(); j++) {
          	if (j == 0) val += 100*v[j].s;
          	if (j == 1) val += 10 * v[j].s;
          	if (j == 2) val += v[j].s;
		  }
		  id[i] = val;
		  //cout<<i<<" "<<val<<endl;
		  ms1[val].insert(i); 
	 }
	//cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<endl;
//	cout<<ans[2]<<endl;
     for (int j = 1; j <= n; j++) {
          for (int i = 1; i <= 3; i++) {
               if (ms.count(a[i][j])) fix[i] = 1;
               ms.erase(a[i][j]);
               ms1[id[a[i][j]]].erase(a[i][j]);
          }
         // cout<<j - 1<<" "<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<endl;
          if (a[1][j] == a[2][j] && a[1][j] == a[3][j]) {
          	 ans1[a[1][j]] += ms.size();
          	 ans[1] += ms1[123].size(); ans[1] += ms1[132].size();
          	 ans[2] += ms1[213].size(); ans[2] += ms1[231].size(); 
			 ans[3] += ms1[321].size(); ans[3] += ms1[312].size();
			 continue;
		  }
		  if (a[1][j] == a[2][j]) {
		       if (bstt[a[1][j]] == j) {
		       	ans1[a[1][j]] += ms.size();
		  	 ans[1] += ms1[123].size(); ans[1] += ms1[312].size(); ans[1] += ms1[132].size();
		  	 ans[2] += ms1[213].size(); ans[2] += ms1[231].size(); ans[2] += ms1[321].size();
		      }
		      if (bstt[a[3][j]] == j) {
		      	ans1[a[3][j]] += ms.size();
		  	 ans[3] += ms1[123].size(); ans[3] += ms1[132].size(); ans[3] += ms1[213].size(); ans[3] += ms1[231].size(); ans[3] += ms1[312].size(); 
			 ans[3] += ms1[321].size();
		      }
			 continue;
		  }
		  if (a[1][j] == a[3][j]) {
		       if (bstt[a[1][j]] == j) {
		            ans1[a[1][j]] += ms.size();
		  	 ans[1] += ms1[123].size(); ans[1] += ms1[132].size(); ans[1] += ms1[213].size();
		  	 ans[3] += ms1[231].size(); ans[3] += ms1[312].size(); ans[3] += ms1[321].size();
		       }
		      if (bstt[a[2][j]] == j) {
		           ans1[a[2][j]] += ms.size();
		  	 ans[2] += ms1[123].size(); ans[2] += ms1[132].size(); ans[2] += ms1[213].size(); ans[2] += ms1[231].size(); ans[2] += ms1[312].size(); 
			 ans[2] += ms1[321].size();
		      }
		//	 cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<endl;
			 continue;
		  }
		  if (a[2][j] == a[3][j]) {
		      //cout<<j<<" "<<ms1[213].size()<<endl;
		      if (bstt[a[2][j]] == j) {
		           ans1[a[2][j]] += ms.size();
		  	 ans[2] += ms1[231].size(); ans[2] += ms1[213].size(); ans[2] += ms1[123].size();
		  	 ans[3] += ms1[321].size(); ans[3] += ms1[312].size(); ans[3] += ms1[132].size(); 
		      }
		      if (bstt[a[1][j]] == j) {
		           ans1[a[1][j]] += ms.size();
		  	 ans[1] += ms1[123].size(); ans[1] += ms1[132].size(); ans[1] += ms1[213].size(); ans[1] += ms1[231].size(); ans[1] += ms1[312].size(); 
			 ans[1] += ms1[321].size();
		      }
			 continue;
		  }if (bstt[a[1][j]] == j)
		  ans[1] += ms.size(), ans1[a[1][j]] += ms.size();
		  if (bstt[a[2][j]] == j) ans[2] += ms.size(), ans1[a[2][j]] += ms.size();
		  if (bstt[a[3][j]] == j) ans[3] += ms.size(), ans1[a[3][j]] += ms.size();
     }
     cout<<ans[1]<<" "<<ans[2]<<" "<<ans[3]<<endl;
     for (int i = 1; i<=n; i++) {
          cout<<ans1[i]<<" ";
     }
}

Compilation message (stderr)

tenis.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main() {
      | ^~~~
tenis.cpp: In function 'int main()':
tenis.cpp:64:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |           for (int j = 0 ; j < v.size(); j++) {
      |                            ~~^~~~~~~~~~
tenis.cpp: In function 'void add(long long int, long long int, long long int)':
tenis.cpp:40:19: warning: 'kk' may be used uninitialized in this function [-Wmaybe-uninitialized]
   40 |            ans[kk]++;
      |            ~~~~~~~^~

• Subtask 1: 35 / 35
• Subtask 2: 15 / 15
• Subtask 3: 60 / 60