Submission #1262120

#TimeUsernameProblemLanguageResultExecution timeMemory
1262120themaver1cksConstruction Project 2 (JOI24_ho_t2)C++17
0 / 100
0 ms324 KiB
/** 。∠(*・ω・)っ ⌒ 由 ~ (( ,,・з・,, )) _Π_____。 /______/~\ | 田田|門| > love miku so muchhhh <3 **/ #include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define sz(x) (int)(x).size() #define el "\n" typedef long long ll; typedef long double ld; typedef pair<int,int> pii; // struct Query { int t, x, y; char c; Query(int _t, int _x, int _y, char _c): t(_t), x(_x), y(_y), c(_c) {}; }; // var dec const int maxn = 1e5 + 3; const ll mod = 1e9 + 7; int n, q; string s; // ds dec vector <Query> queries; // namespace sub1 { bool condition() { return (max(n, q) <= 15); } // void solve() { vector <string> saved(q+1); for (int z=0; z<q; ++z) { int t = queries[z].t, x = queries[z].x, y = queries[z].y; char c = queries[z].c; if (t == 1) { s[x] = c; } else if (t == 2) { int d = y-x+1; int ans = 0; for (int mask=0; mask<(1<<d); ++mask) { string temp = ""; int cnt = __builtin_popcount(mask); if (cnt != 5) continue; for (int j=0; j<d; ++j) { if (mask & (1<<j)) { temp += s[x+j]; } } if (temp == "HSGQG") ans++; } cout << ans << el; } else { s = saved[x]; } saved[z+1] = s; } } } // namespace sub2 { bool condition() { return (n <= 1000 && q == 1 && queries[0].t == 2 && queries[0].x == 1 && queries[0].y == n); } // void solve() { string tdk = "HSGQG"; vector <vector<ll>> dp(5, vector<ll>(n+3, 0)); for (int i=1; i<=n; ++i) { for (int k=0; k<5; ++k) { int cnt = 0; if (k == 0 && s[i] == tdk[k]) dp[k][i] = 1; else if (s[i] == tdk[k]) { for (int j=i-1; j>=1; --j) { if (s[j] == tdk[k-1]) { dp[k][i] += dp[k-1][j]; if (dp[k][i] > mod) dp[k][i] -= mod; } } } } } // for (int k=0; k<5; ++k) // { // cout << k << ": "; // for (int i=1; i<=n; ++i) cout << dp[k][i] << " "; // cout << el; // } ll ans = 0; for (int i=1; i<=n; ++i) (ans += dp[4][i]) %= mod; cout << ans << el; } } // void solve() { cin >> n >> q; cin >> s; s = "#" + s; for (int i=1; i<=q; ++i) { int t; cin >> t; if (t == 1) { int x; char c; cin >> x >> c; queries.pb(Query(1, x, -1, c)); } else if (t == 2) { int x, y; cin >> x >> y; queries.pb(Query(2, x, y, '0')); } else { int x; cin >> x; queries.pb(Query(3, x, -1, '0')); } } if (sub2::condition()) sub2::solve(); else sub1::solve(); } // int32_t main() { ios_base::sync_with_stdio(false); cin.tie(0); if (fopen("hsgqg.inp", "r")) { freopen("hsgqg.inp", "r", stdin); freopen("hsgqg.out", "w", stdout); } int t = 1; // cin >> t; while (t--) solve(); return 0; }

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:160:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  160 |         freopen("hsgqg.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:161:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |         freopen("hsgqg.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...