Submission #895561

#	Time	Username	Problem	Language	Result	Execution time	Memory
895561		d4xn	Cards (LMIO19_korteles)	C++17	100 / 100	745 ms	48212 KiB

korteles

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()
#define tp4 tuple<int, int, int, int>

const int N = 456976, D = 27, inf = INT_MAX;

int n, ans, dp[D][D][D][D];
string a[2][N], b[N];

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  for (int i = 0; i < D; i++) {
    for (int j = 0; j < D; j++) {
      for (int k = 0; k < D; k++) {
        memset(dp[i][j][k], 0, sizeof(dp[i][j][k]));
      }
    }
  }

  vector<tp4> comb(4);
  comb[0] = make_tuple(0, 1, 2, 3);
  comb[1] = make_tuple(1, 3, 0, 2);
  comb[2] = make_tuple(0, 2, 1, 3);
  comb[3] = make_tuple(2, 3, 0, 1);

  cin >> n;
  ans = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[0][i] >> a[1][i];
    b[i] = a[0][i] + a[1][i];

    // con cuantas de antes combina esta carta?

    for (int mask = 1; mask < (1 << 4); mask++) {
      vector<int> eq[4];
      for (int j = 0; j < 4; j++) {
        if (!((mask >> j) & 1)) continue;
        eq[get<2>(comb[j])].push_back(get<0>(comb[j]));
        eq[get<3>(comb[j])].push_back(get<1>(comb[j]));
      }
 
      bool ok = 1;
      int nwEq[4] = {D-1, D-1, D-1, D-1};
      for (int j = 0; j < 4 && ok; j++) {
        int sz = eq[j].size();
        for (int k = 1; k < sz; k++) {
          //cerr << j << " eq " << eq[j][k] << endl;
          if (b[i][eq[j][k]] != b[i][eq[j][0]]) {
            ok = 0;
            break;
          }
        }
        if (sz) nwEq[j] = (int)(b[i][eq[j][0]]-'A');
      }
      if (!ok) continue;

      /*cerr << i << " nwEq " << __builtin_popcount(mask) << endl;
      for (int j = 0; j < 4; j++) {
        cerr << nwEq[j] << " ";
      }
      cerr << endl;*/

      ans += dp[nwEq[0]][nwEq[1]][nwEq[2]][nwEq[3]] * (__builtin_popcount(mask)%2 ? 1 : -1);
    }

    // añado esta carta
    for (int mask = 1; mask < (1 << 4); mask++) {
      int x[4];
      //cerr << "x ";
      for (int j = 0; j < 4; j++) {
        x[j] = (((mask >> j) & 1) ? (int)(b[i][j]-'A') : D-1);
        //cerr << x[j] << " ";
      }
      //cerr << endl;
      dp[x[0]][x[1]][x[2]][x[3]]++;
    }//cerr << ans << endl;
  }

  cout << ans << "\n";
}

• Subtask 1: 16 / 16
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 19 / 19
• Subtask 5: 25 / 25