| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 135436 | 2019-07-24T05:37:44 Z | 윤교준(#3250) | PIN (CEOI10_pin) | C++14 | 698 ms | 7736 KB |
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[sz(V)-2])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int B[36][36][36][36];
int A[50005][4];
ll Ans;
int N, K;
ll preans = -1;
ll solve2() {
if(0 <= preans) return preans;
ll ret = 0;
for(int i = 0; i < N; i++) {
int a = A[i][0], b = A[i][1], c = A[i][2], d = A[i][3];
for(int j = 0; j < 36; j++) if(j != a) {
for(int k = 0; k < 36; k++) {
if(k != b) ret += B[j][k][c][d];
if(k != c) ret += B[j][b][k][d];
if(k != d) ret += B[j][b][c][k];
}
}
for(int j = 0; j < 36; j++) if(j != b) {
for(int k = 0; k < 36; k++) {
if(k != c) ret += B[a][j][k][d];
if(k != d) ret += B[a][j][c][k];
}
}
for(int j = 0; j < 36; j++) if(j != c) {
for(int k = 0; k < 36; k++) if(k != d)
ret += B[a][b][j][k];
}
}
return preans = (ret >> 1);
}
ll solve1() {
int ret = 0;
for(int i = 0; i < N; i++) {
int a = A[i][0], b = A[i][1], c = A[i][2], d = A[i][3];
for(int j = 0; j < 36; j++) {
if(j != a) ret += B[j][b][c][d];
if(j != b) ret += B[a][j][c][d];
if(j != c) ret += B[a][b][j][d];
if(j != d) ret += B[a][b][c][j];
}
}
return ret >> 1;
}
int C[4][36];
ll solve4() {
ll ret = ll(N) * (N-1) >> 1;
ll d2 = solve2(), d1 = solve1();
for(int i = 0; i < N; i++) {
for(int j = 0; j < 4; j++)
C[j][A[i][j]]++;
}
ll one = 0;
for(int i = 0; i < 4; i++) {
for(int j = 0; j < 36; j++) {
one += (ll(C[i][j]) * (C[i][j]-1)) >> 1;
}
}
one -= d2 + (d1<<1);
return ret - one;
}
ll solve3() {
return (ll(N) * (N-1) >> 1) - solve1() - solve2() - solve4();
}
int main() {
scanf("%d%d", &N, &K);
for(int i = 0; i < N; i++) {
char str[5]; scanf(" %s", str);
for(int j = 0; j < 4; j++) {
if('0' <= str[j] && str[j] <= '9')
A[i][j] = str[j] & 15;
else A[i][j] = str[j] - 'a' + 10;
}
B[A[i][0]][A[i][1]][A[i][2]][A[i][3]]++;
}
if(1 == K) Ans = solve1();
else if(2 == K) Ans = solve2();
else if(3 == K) Ans = solve3();
else Ans = solve4();
cout << Ans << endl;
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 1628 KB | Output is correct |
| 2 | Correct | 17 ms | 1656 KB | Output is correct |
| 3 | Correct | 14 ms | 1656 KB | Output is correct |
| 4 | Correct | 10 ms | 1912 KB | Output is correct |
| 5 | Correct | 12 ms | 2012 KB | Output is correct |
| 6 | Correct | 212 ms | 2076 KB | Output is correct |
| 7 | Correct | 165 ms | 1912 KB | Output is correct |
| 8 | Correct | 13 ms | 2020 KB | Output is correct |
| 9 | Correct | 19 ms | 2424 KB | Output is correct |
| 10 | Correct | 420 ms | 2468 KB | Output is correct |
| 11 | Correct | 226 ms | 2104 KB | Output is correct |
| 12 | Correct | 412 ms | 2420 KB | Output is correct |
| 13 | Correct | 259 ms | 2156 KB | Output is correct |
| 14 | Correct | 233 ms | 2112 KB | Output is correct |
| 15 | Correct | 400 ms | 2428 KB | Output is correct |
| 16 | Correct | 23 ms | 7492 KB | Output is correct |
| 17 | Correct | 676 ms | 7736 KB | Output is correct |
| 18 | Correct | 551 ms | 7524 KB | Output is correct |
| 19 | Correct | 635 ms | 7628 KB | Output is correct |
| 20 | Correct | 698 ms | 7708 KB | Output is correct |