Submission #1052223

#TimeUsernameProblemLanguageResultExecution timeMemory
1052223crafticatCrossing (JOI21_crossing)C++17
100 / 100
833 ms41508 KiB
#include <bits/stdc++.h> using namespace std; #include <bits/stdc++.h> #include <utility> using namespace std; using ll = long long; using pi = pair<int,int>; using pl = pair<ll,ll>; #define temp(T) template<class T> temp(T) using V = vector<T>; using vi = V<int>; using vl = V<ll>; using vvi = V<vi>; using vpi = V<pi>; using vb = V<bool>; using vvb = V<vb>; vi dx = {0,1,-1,0}; vi dy = {1,0,0,-1}; #define sz(x) x.size() #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) #define sor(x) sort(all(x)) #define rsz resize #define ins insert #define pb push_back #define eb emplace_back #define f first #define s second #define lb lower_bound #define ub upper_bound #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define rep(a) F0R(_,a) #define each(a,x) for (auto& a: x) using str = string; const int MOD = 1e9 + 7; const ll BIG = 1e18; const int INF = 1e9 + 2; temp(T) bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b) temp(T) bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; } // set a = max(a,b) void unsyncIO() { cin.tie(0)->sync_with_stdio(0); } // FILE I/O void setIn(str s) { freopen(s.c_str(),"r",stdin); } void setOut(str s) { freopen(s.c_str(),"w",stdout); } void setIO(str s = "") { unsyncIO(); if (sz(s)) setIn(s+".in"), setOut(s+".out"); // for USACO } #define read(x) int x; cin >> x temp(T) void pr(T x) { cout << to_string(x); } temp(T) void prln(T x) { cout << to_string(x) << "\n"; } vi readV(int n) { vi input(n); F0R(i,n) cin >> input[i]; return input; } int rand(int a, int b) { return a + rand() % (b - a + 1); } #define gen(x,a,b) int x = rand(a,b) temp(T) void moveAll(V<T> &a, V<T> &b) { each(x,b) { a.pb(x); } b.clear(); } vi genArr(int n, int a, int b) { vi generated(n); F0R(i,n) { generated[i] = rand(a,b); } return generated; } vvi genTree(int n) { vvi g(n + 1); F0R(i,n) { gen(p,0,i); g[p].pb(i + 1); g[i + 1].pb(p); } return g; } vvb readGrid(int a, int b) { vvb grid(a + 2, vb(b + 2, true)); F0R(i, a) { F0R(j, b) { bool k; cin >> k; grid[i + 1][j + 1] = k; } } return grid; } struct mint { ll v; mint(ll t) : v(t % MOD) {} mint() = default; mint operator*(mint other) { return {v * other.v}; } void operator*=(mint other) { v *= other.v; v %= MOD; } mint operator+(mint other) { return {v + other.v}; } void operator+=(mint other) { v += other.v; v %= MOD; } }; V<V<mint>> prePrefix; V<V<mint>> prePrefix2; // TODO precompute mint pow(mint a, int b) { if (b == 0) return 1; mint ans = pow(a, b / 2); ans = ans * ans; if (b % 2) ans *= a; return ans; } int v(char k) { if (k == 'O') return 0; if (k == 'I') return 1; if (k == 'J') return 2; exit(5); } struct Seg { Seg *left = nullptr, *right = nullptr; int l, r, mid; mint hash = 0; mint hash2 = 0; int lazy = -1; Seg(int l, int r, str &def) : l(l) ,r(r), mid((r + l) / 2) { if (r -l > 1) { left = new Seg(l,mid,def); right = new Seg(mid,r,def); hash = left->hash + right->hash * pow(mint(3), mid - l); hash2 = left->hash2 + right->hash2 * pow(mint(4), mid - l); } else { hash = v(def[l]); hash2 = v(def[l]); } } void push() { if (lazy != -1) { hash = prePrefix[lazy][r - l]; hash2 = prePrefix2[lazy][r - l]; if (r - l > 1) { left->lazy = lazy; right->lazy = lazy; } lazy = -1; } } void update(int a, int b, int k) { push(); if (b <= l || a >= r) return; if (a <= l && b >= r) { lazy = k; push(); return; } left->update(a,b,k); right->update(a,b,k); hash = left->hash + right->hash * pow(mint(3), mid - l); hash2 = left->hash2 + right->hash2 * pow(mint(4), mid - l); } }; using has = pair<mint,mint>; has findHash(str a) { mint h = 0; mint h2 = 0; mint power = 1; mint power2 = 1; F0R(i, sz(a)) { h += power * v(a[i]); h2 += power2 * v(a[i]); power *= 3; power2 *= 4; } return {h, h2}; } str add(str a, str b) { str c = a; F0R(i, sz(a)) { if (a[i] == b[i]) continue; if ('O' != a[i] and 'O' != b[i]) c[i] = 'O'; if ('J' != a[i] and 'J' != b[i]) c[i] = 'J'; if ('I' != a[i] and 'I' != b[i]) c[i] = 'I'; } return c; } V<has> hashes; void genHashes(str a, str b, str c) { set<str> found; str acc = a; while (!found.count(acc)) { found.ins(acc); acc = add(acc,a); hashes.pb(findHash(acc)); acc = add(acc,b); hashes.pb(findHash(acc)); acc = add(acc,c); hashes.pb(findHash(acc)); } } bool findMatch(has hash) { each(x, hashes) { if (x.f.v ==hash.f.v && x.s.v == hash.s.v) return true; } return false; } int main() { setIO(); int n; cin >> n; V<str> starts(3); F0R(i, 3) { cin >> starts[i]; } int q; cin >> q; string def; cin >> def; Seg seg(0, sz(def), def); vi perm = {0,1,2}; do { genHashes(starts[perm[0]], starts[perm[1]], starts[perm[2]]); } while (next_permutation(all(perm))); prePrefix.rsz(3, V<mint>(n + 1)); prePrefix2.rsz(3, V<mint>(n + 1)); F0R(i, 3) { mint h = 0; mint h2 = 0; mint power = 1; mint power2 = 1; F0R(j, n + 1) { prePrefix[i][j] = h; prePrefix2[i][j] = h2; h += power * (i); h2 += power2 * (i); power *= 3; power2 *= 4; } } cout << ((findMatch({seg.hash,seg.hash2})) ? "Yes" : "No") << "\n"; F0R(i, q) { int l, r; cin >> l >> r; l--; char c; cin >> c; seg.update(l, r, v(c)); cout << ((findMatch({seg.hash,seg.hash2})) ? "Yes" : "No") << "\n"; } return 0; }

Compilation message (stderr)

Main.cpp: In function 'has findHash(str)':
Main.cpp:39:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
Main.cpp:40:18: note: in expansion of macro 'FOR'
   40 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
Main.cpp:222:5: note: in expansion of macro 'F0R'
  222 |     F0R(i, sz(a)) {
      |     ^~~
Main.cpp: In function 'str add(str, str)':
Main.cpp:39:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 | #define FOR(i,a,b) for (int i = (a); i < (b); ++i)
      |                                        ^
Main.cpp:40:18: note: in expansion of macro 'FOR'
   40 | #define F0R(i,a) FOR(i,0,a)
      |                  ^~~
Main.cpp:233:5: note: in expansion of macro 'F0R'
  233 |     F0R(i, sz(a)) {
      |     ^~~
Main.cpp: In function 'void setIn(str)':
Main.cpp:59:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 | void setIn(str s) { freopen(s.c_str(),"r",stdin); }
      |                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp: In function 'void setOut(str)':
Main.cpp:60:29: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 | void setOut(str s) { freopen(s.c_str(),"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...