Submission #435160
Source Code Expand
#include <iostream> #include <cstdio> #include <cassert> #include <cstring> #include <vector> #include <valarray> #include <array> #include <queue> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <algorithm> #include <cmath> #include <complex> #include <random> using namespace std; typedef long long ll; typedef unsigned long long ull; const int MN = 32; const int MM = 200; int n, m; int x[MM], y[MM]; int z[MN][4]; int zc[MN]; int zcsm[MN], mc[MN]; int d[MN]; int p = 0; int ma = -1; int res = 0; void dfs(int i) { // printf("dfs %d/%d %d %d\n", i, n, ma, res); if (i == n) { if (ma < p) { ma = p; res = 1; } else if (ma == p) { res++; } return; } if (p + zcsm[i] < ma) return; int co[2] = {}; for (int j = 0; j < zc[i]; j++) { if (i < z[i][j]) continue; if (d[z[i][j]]) co[0]++; else co[1]++; } if (co[0] > co[1]) { d[i] = 0; p += co[0]; dfs(i+1); p -= co[0]; if (co[1]+mc[i] < co[0]) return; d[i] = 1; p += co[1]; dfs(i+1); p -= co[1]; } else { d[i] = 1; p += co[1]; dfs(i+1); p -= co[1]; if (co[0]+mc[i] < co[1]) return; d[i] = 0; p += co[0]; dfs(i+1); p -= co[0]; } } int solve() { for (int i = 0; i < m; i++) { int xx = x[i], yy = y[i]; if (xx < yy) swap(xx, yy); z[xx][zc[xx]] = yy; zc[xx]++; mc[yy]++; } zcsm[n] = 0; for (int i = n-1; i >= 0; i--) { zcsm[i] = zcsm[i+1] + zc[i]; } dfs(0); return res; } int main() { string s; cin >> s; int mc = (int)s.size()+1; mc /= 4; char in[MM][2]; m = 0; set<char> allc; for (int i = 0; i < mc; i++) { in[m][0] = s[4*i]; in[m][1] = s[4*i+2]; allc.insert(in[m][0]); allc.insert(in[m][1]); if (in[m][0] == in[m][1]) continue; m++; } map<char, int> mp; n = 0; for (int i = 0; i < m; i++) { if (!mp.count(in[i][0])) { mp[in[i][0]] = n; n++; } if (!mp.count(in[i][1])) { mp[in[i][1]] = n; n++; } } int k = 1 << (allc.size()-n); for (int i = 0; i < m; i++) { x[i] = mp[in[i][0]]; y[i] = mp[in[i][1]]; } cout << k*solve() << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | L - セミ時雨ハッシュ |
User | yosupo |
Language | C++11 (GCC 4.9.2) |
Score | 300 |
Code Size | 2634 Byte |
Status | AC |
Exec Time | 1785 ms |
Memory | 932 KB |
Judge Result
Set Name | Subtask | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 270 / 270 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask | subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt |
All | scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, scrambled_33.txt, scrambled_34.txt, scrambled_35.txt, scrambled_36.txt, scrambled_37.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
scrambled_00.txt | AC | 26 ms | 916 KB |
scrambled_01.txt | AC | 24 ms | 812 KB |
scrambled_02.txt | AC | 34 ms | 924 KB |
scrambled_03.txt | AC | 66 ms | 800 KB |
scrambled_04.txt | AC | 32 ms | 804 KB |
scrambled_05.txt | AC | 36 ms | 800 KB |
scrambled_06.txt | AC | 42 ms | 800 KB |
scrambled_07.txt | AC | 32 ms | 924 KB |
scrambled_08.txt | AC | 28 ms | 928 KB |
scrambled_09.txt | AC | 34 ms | 920 KB |
scrambled_10.txt | AC | 40 ms | 812 KB |
scrambled_11.txt | AC | 37 ms | 920 KB |
scrambled_12.txt | AC | 36 ms | 808 KB |
scrambled_13.txt | AC | 1785 ms | 920 KB |
scrambled_14.txt | AC | 28 ms | 796 KB |
scrambled_15.txt | AC | 27 ms | 920 KB |
scrambled_16.txt | AC | 29 ms | 920 KB |
scrambled_17.txt | AC | 26 ms | 924 KB |
scrambled_18.txt | AC | 27 ms | 728 KB |
scrambled_19.txt | AC | 27 ms | 920 KB |
scrambled_20.txt | AC | 27 ms | 916 KB |
scrambled_21.txt | AC | 26 ms | 924 KB |
scrambled_22.txt | AC | 25 ms | 796 KB |
scrambled_23.txt | AC | 23 ms | 916 KB |
scrambled_24.txt | AC | 26 ms | 732 KB |
scrambled_25.txt | AC | 25 ms | 920 KB |
scrambled_26.txt | AC | 23 ms | 924 KB |
scrambled_27.txt | AC | 25 ms | 924 KB |
scrambled_28.txt | AC | 26 ms | 796 KB |
scrambled_29.txt | AC | 26 ms | 796 KB |
scrambled_30.txt | AC | 27 ms | 920 KB |
scrambled_31.txt | AC | 28 ms | 920 KB |
scrambled_32.txt | AC | 31 ms | 924 KB |
scrambled_33.txt | AC | 34 ms | 912 KB |
scrambled_34.txt | AC | 26 ms | 800 KB |
scrambled_35.txt | AC | 27 ms | 808 KB |
scrambled_36.txt | AC | 27 ms | 812 KB |
scrambled_37.txt | AC | 26 ms | 804 KB |
subtask_00.txt | AC | 24 ms | 804 KB |
subtask_01.txt | AC | 24 ms | 924 KB |
subtask_02.txt | AC | 24 ms | 924 KB |
subtask_03.txt | AC | 24 ms | 924 KB |
subtask_04.txt | AC | 26 ms | 932 KB |
subtask_05.txt | AC | 24 ms | 804 KB |
subtask_06.txt | AC | 24 ms | 928 KB |
subtask_07.txt | AC | 24 ms | 928 KB |
subtask_08.txt | AC | 24 ms | 920 KB |
subtask_09.txt | AC | 27 ms | 752 KB |
subtask_10.txt | AC | 25 ms | 804 KB |
subtask_11.txt | AC | 25 ms | 804 KB |