oj.uz

Submission #598872

# Submission time Handle Problem Language Result Execution time Memory
598872 2022-07-19T06:43:11 Z shrimb Cards (LMIO19_korteles) C++17
36 / 100
 1000 ms 225488 KB 
#include"bits/stdc++.h"
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class x>
using ordered_set = tree<x, null_type,less_equal<x>, rb_tree_tag,tree_order_statistics_node_update>;

#define int long long
#define endl '\n'
#define mod 1000000007

//\
#define mod 1686876991

int Hash (int a, int b) {
	return ((a-'A' +1 ) * 26) % mod + (b - 'A'+1);
}

unordered_map<int,int> mp[1<<4];
signed main () {
	for (auto& i : mp) i.reserve(1000000);
    cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	int ans = 0;
	int inc[16];
	for (int i = 0 ; i < n ; i++) {
		char a, b, c, d;
		cin >> a >> b >> c >> d;
		int H[4] = {Hash(a, b), Hash(b, d), Hash(c, d), Hash(a, c)};
		// U R D L

		int cnt = 0;
		int inv = 0;
		#define check(j,i,k) if (j & (1 << i)) { cnt++; enc = (enc * 26 * 26 + H[i])%mod; inv |= (1 << k);}
		for (int j = 1 ; j < (1 << 4) ; j++) {
			int enc = 0, ienc = 0;
			cnt = 0;
			inv = 0;
			check(j, 0, 2);
			check(j, 1, 3);
			check(j, 2, 0);
			check(j, 3, 1);
			for (int k = 0 ; k < 4 ; k++) {
				if (inv & (1 << k)) {
					ienc = (ienc * 26 *26 + H[(k + 2) % 4])%mod;
				}
			}
			if (cnt & 1) ans += mp[inv][ienc];
			else ans -= mp[inv][ienc];
			// cerr << enc << endl;
			inc[j] = enc;
		}
		for (int j = 1 ; j < (1 << 4) ; j++) mp[j][inc[j]]++;
	}
	cout << ans << endl;
}

Compilation message

korteles.cpp:15:1: warning: multi-line comment [-Wcomment]
   15 | //\
      | ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 132560 KB Output is correct
2 Correct 73 ms 132604 KB Output is correct
3 Correct 72 ms 132660 KB Output is correct
4 Correct 83 ms 132720 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 132560 KB Output is correct
2 Correct 73 ms 132604 KB Output is correct
3 Correct 72 ms 132660 KB Output is correct
4 Correct 83 ms 132720 KB Output is correct
5 Correct 75 ms 132556 KB Output is correct
6 Correct 75 ms 133080 KB Output is correct
7 Correct 96 ms 133280 KB Output is correct
8 Correct 94 ms 134348 KB Output is correct
9 Correct 84 ms 133984 KB Output is correct
10 Correct 95 ms 133948 KB Output is correct
11 Correct 90 ms 132616 KB Output is correct

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1096 ms 225488 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 132616 KB Output is correct
2 Incorrect 337 ms 157920 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 132556 KB Output is correct
2 Correct 75 ms 133080 KB Output is correct
3 Correct 96 ms 133280 KB Output is correct
4 Correct 94 ms 134348 KB Output is correct
5 Correct 84 ms 133984 KB Output is correct
6 Correct 95 ms 133948 KB Output is correct
7 Correct 90 ms 132616 KB Output is correct
8 Correct 74 ms 132560 KB Output is correct
9 Correct 73 ms 132604 KB Output is correct
10 Correct 72 ms 132660 KB Output is correct
11 Correct 83 ms 132720 KB Output is correct
12 Execution timed out 1096 ms 225488 KB Time limit exceeded
13 Halted 0 ms 0 KB -