Submission #399382

#	Time	Username	Problem	Language	Result	Execution time	Memory
399382		retsiger	Tenis (COCI20_tenis)	C++14	55 / 110	181 ms	11740 KiB

tenis

#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 = 0; 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: 17.5 / 35
• Subtask 2: 7.5 / 15
• Subtask 3: 30 / 60