oj.uz

Submission #399383

# Submission time Handle Problem Language Result Execution time Memory
399383 2021-05-05T16:06:20 Z retsiger Tenis (COCI20_tenis) C++14
110 / 110
 159 ms 11704 KB 
#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';
}

Subtask #1
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 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 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 588 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 4 ms 588 KB Output is correct
5 Correct 55 ms 4852 KB Output is correct
6 Correct 85 ms 7108 KB Output is correct
7 Correct 118 ms 9352 KB Output is correct
8 Correct 155 ms 11704 KB Output is correct
9 Correct 159 ms 11192 KB Output is correct
10 Correct 127 ms 8436 KB Output is correct