#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
const int man = (int)(1e5 + 500);
int n;
int courts[man], lose[man], mn[man];
int a[3][man], loc[3][man];
vector <int> v[8];
map <pair <int, int>, pair <int, int> > mp;
map <pair <int, int>, bool> was;
void check(int x, int t1, int t2) {
if ((t1 == t2) || (loc[t1][x] != mn[x])) {
return;
}
int y = loc[t2][mn[x]];
if ((mn[y] != mn[x]) || (x == y)) {
return;
}
// cerr << (t1 + 1) << " " << (t2 + 1) << " " << (x + 1) << " " << (y + 1) << "\n";
int xx = x, yy = y;
if (xx > yy) {
swap(xx, yy);
}
if (loc[t1][y] < mn[x]) {
return;
}
if (!was[{xx, yy}]) {
was[{xx, yy}] = true;
if (loc[t1][y] < loc[t2][x]) {
mp[{xx, yy}] = {loc[t1][y], t1};
} else if (loc[t2][x] < loc[t1][y]) {
mp[{xx, yy}] = {loc[t2][x], t2};
} else {
if (t1 < t2) {
mp[{xx, yy}] = {loc[t1][y], t1};
} else {
mp[{xx, yy}] = {loc[t2][x], t2};
}
}
} else {
pair <int, int> c1, c2 = mp[{xx, yy}];
if (loc[t1][y] < loc[t2][x]) {
c1 = {loc[t1][y], t1};
} else if (loc[t2][x] < loc[t1][y]) {
c1 = {loc[t2][x], t2};
} else {
if (t1 < t2) {
c1 = {loc[t1][y], t1};
} else {
c1 = {loc[t2][x], t2};
}
}
mp[{xx, yy}] = min(c1, c2);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
mn[i] = n;
}
for (int t = 0; t < 3; ++t) {
for (int i = 0; i < n; ++i) {
int& x = a[t][i];
cin >> x;
--x;
loc[t][x] = i;
mn[x] = min(mn[x], i);
}
}
cerr << "\n";
for (int i = 0; i < n; ++i) {
int msk = 0;
for (int t = 0; t < 3; ++t) {
if (mn[i] == loc[t][i]) {
msk |= (1 << t);
}
}
v[msk].push_back(mn[i]);
}
for (int i = 0; i < 8; ++i) {
sort(v[i].begin(), v[i].end());
}
for (int i = 0; i < n; ++i) {
for (int msk = 1; msk < 8; ++msk) {
int ps = lower_bound(v[msk].begin(), v[msk].end(), mn[i]) - v[msk].begin();
int wn = -1;
for (int t = 0; t < 3; ++t) {
if ((msk >> t) & 1) {
if ((wn == -1) || (loc[t][i] < loc[wn][i])) {
wn = t;
}
}
}
// cerr << i << " " << ps << " " << wn << " " << msk << "\n";
courts[wn] += ps;
lose[i] += ps;
}
}
// for (int i = 0; i < 3; ++i) {
// cerr << courts[i] << " ";
// }
// cerr << "\n";
// for (int i = 0; i < n; ++i) {
// cerr << lose[i] << " ";
// }
// cerr << "\n\n";
for (int i = 0; i < n; ++i) {
for (int t1 = 0; t1 < 3; ++t1) {
for (int t2 = 0; t2 < 3; ++t2) {
check(i, t1, t2);
}
}
}
for (auto& i : mp) {
// cerr << (i.first.first + 1) << " " << (i.first.second + 1) << " " << (a[i.second.second][i.second.first] + 1) << " " << (i.second.second + 1) << "\n";
++courts[i.second.second];
++lose[a[i.second.second][i.second.first]];
}
for (int i = 0; i < 3; ++i) {
cout << courts[i] << " ";
}
cout << "\n";
for (int i = 0; i < n; ++i) {
cout << (n - 1 - lose[i]) << " ";
}
cout << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
