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 int long long
#define x first
#define y second
#define bug(x) cerr<<#x<<" = "<<x<<'\n'
using namespace std;
typedef pair <int, int> ii;
const int maxn = 100100;
int N, A[3][maxn], loc[maxn][3];
int cn[3], pt[maxn], bestPos[maxn];
vector <int> buck[8];
map <ii, int> mp;
void solve(int i, int j, int pos) {
if (i == j || bestPos[i] != pos || bestPos[j] != pos) return;
if (i > j) swap(i, j);
if (mp[ii(i, j)]) return;
mp[ii(i, j)] = 1;
vector<array<int, 3>> v;
for (int t = 0; t < 3; ++t) {
int x = min(loc[i][t], loc[j][t]);
int y = max(loc[i][t], loc[j][t]);
v.push_back({x, y, t});
}
sort(v.begin(), v.end());
auto p = v[0];
if (p[0] == loc[i][p[2]]) pt[j]++;
else pt[i]++;
cn[p[2]]++;
}
signed main() {
ios::sync_with_stdio(0); cin.tie(0);
// freopen("cc.inp", "r", stdin);
// freopen("cc.out", "w", stdout);
cin >> N;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < N; ++j) {
cin >> A[i][j];
--A[i][j];
loc[A[i][j]][i] = j;
}
}
for (int i = 0; i < N; ++i) {
bestPos[i] = min({loc[i][0], loc[i][1], loc[i][2]});
int msk = 0;
for (int j = 0; j < 3; ++j) {
if (loc[i][j] == bestPos[i]) msk |= (1 << j);
}
buck[msk].push_back(bestPos[i]);
}
for (int i = 1; i < 8; ++i)
sort(buck[i].begin(), buck[i].end());
for (int i = 0; i < N; ++i) {
solve(A[0][i], A[1][i], i);
solve(A[0][i], A[2][i], i);
solve(A[1][i], A[2][i], i);
for (int msk = 1; msk < 8; ++msk) {
int p = lower_bound(buck[msk].begin(), buck[msk].end(), bestPos[i]) - buck[msk].begin();
int crt = -1;
for (int j = 0; j < 3; ++j) if (msk >> j & 1) {
if (crt == -1 || loc[i][j] < loc[i][crt]) crt = j;
}
cn[crt] += p;
pt[i] += p;
}
}
for (int i = 0; i < 3; ++i) cout << cn[i] << ' ';
cout << '\n';
for (int i = 0; i < N; ++i) cout << N - 1 - pt[i] << ' ';
cout << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |