| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 480424 | lukameladze | Xoractive (IZhO19_xoractive) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
# 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]<<" ";
}
}