Codeforces Round #866 (Div.1, Div.2, based on Lipetsk Team Olympiad) Editorial
Разница между en1 и en2, 22,873 символ(ов) изменены
[problem:1820A]↵

Author: [user:FairyWinx,2023-04-16]↵

Preparation: [user:FairyWinx,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1820A]↵
</spoiler>↵

[problem:1820B]↵

Author: [user:golikovnik,2023-04-16]↵

Preparation: [user:teraqqq,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1820B]↵
</spoiler>↵

[problem:1819A]↵

Author: [user:TeaTime,2023-04-16]↵

Preparation: [user:golikovnik,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819A]↵
</spoiler>↵

[problem:1819B]↵

Author: [user:Tikhon228,2023-04-16]↵

Preparation: [user:Kon567889,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819B]↵
</spoiler>↵

[problem:1819C]↵

Author: [user:golikovnik,2023-04-16]↵

Preparation: [user:DishonoredRighteous,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819C]↵
</spoiler>↵

[problem:1819D]↵

Author: [user:Um_nik,2023-04-16]↵

Preparation: [user:dshindov,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819D]↵
</spoiler>↵

[problem:1819E]↵

Author: [user:Tikhon228,2023-04-16]↵

Preparation: [user:grphil,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819E]↵
</spoiler>↵

[problem:1819F]↵

Author: [user:teraqqq,2023-04-16]↵

Preparation: [user:teraqqq,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819F]
<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

int main() {↵
    int t;↵
    cin >> t;↵
    while (t--) {↵
        string s;↵
        cin >> s;↵
        if (s == "^") {↵
            cout << 1 << '\n';↵
            continue;↵
        }↵
        int ans = 0;↵
        if (s[0] == '_')↵
            ++ans;↵
        if (s.back() == '_')↵
            ++ans;↵
        for (int i = 0; i < (int) s.size() - 1; ++i) {↵
            if (s[i] == '_' && s[i + 1] == '_')↵
                ++ans;↵
        }↵
        cout << ans << '\n';↵
    }↵
}↵
~~~~~↵
</spoiler>↵

[problem:1820B]↵

Author: [user:golikovnik,2023-04-16]↵

Preparation: [user:teraqqq,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1820B]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵
using ll = long long;↵

int main() {↵
    ios::sync_with_stdio(0); cin.tie(0);↵

    int t = 1;↵
    cin >> t;↵
    while (t--) {↵
        string s; cin >> s; s += s;↵
        int k = 0, z = 0;↵
        for (char c : s) {↵
            z = c == '1' ? z+1 : 0;↵
            k = max(k, z);↵
        }↵
        const int n = s.size() / 2;↵

        if (k > n) {↵
            cout << (ll)n*n << '\n';↵
        } else {↵
            const ll side_a = (k+1)/2;↵
            const ll side_b = (k+2)/2;↵
            cout << side_a * side_b << '\n';↵
        }↵
    }↵
}↵
~~~~~↵
</spoiler>↵

[problem:1819A]↵

Author: [user:TeaTime,2023-04-16]↵

Preparation: [user:golikovnik,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819A]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
//  Nikita Golikov, 2023↵

#include <bits/stdc++.h>↵

using namespace std;↵

using uint = unsigned int;↵
using ll = long long;↵
using ull = unsigned long long;↵

#ifdef GOLIKOV↵
    #define debug(x) cerr << (#x) << ":\t" << (x) << endl↵
#else↵
    #define debug(x) 238;↵
#endif↵

template <class A, class B>↵
bool smin(A& x, B&& y) {↵
  if (y < x) {↵
    x = y;↵
    return true;↵
  }↵
  return false;↵
}↵

template <class A, class B>↵
bool smax(A& x, B&& y) {↵
  if (x < y) {↵
    x = y;↵
    return true;↵
  }↵
  return false;↵
}↵

template <class T>↵
int calcMex(vector<T> v) {↵
  sort(v.begin(), v.end());↵
  v.erase(unique(v.begin(), v.end()), v.end());↵
  int n = int(v.size());↵
  for (int i = 0; i < n; ++i) if (v[i] != i) return i;↵
  return n;↵
}↵

bool solveTest() {↵
  int n; cin >> n;↵
  vector<int> a(n);↵
  map<int, int> leftOcc, rightOcc;↵
  for (int i = 0; i < n; ++i) {↵
    cin >> a[i];↵
    rightOcc[a[i]] = i;↵
    if (!leftOcc.count(a[i])) leftOcc[a[i]] = i;↵
  }↵
  int mex = calcMex(a);↵
  if (leftOcc.count(mex + 1)) {↵
    int L = leftOcc[mex + 1], R = rightOcc[mex + 1];↵
    for (int i = L; i <= R; ++i) {↵
      a[i] = mex;↵
    }↵
    int mx = calcMex(a);↵
    assert(mx <= mex + 1);↵
    return mx == mex + 1;↵
  }↵
  for (int i = 0; i < n; ++i) {↵
    assert(a[i] != mex);↵
    if (a[i] > mex || (leftOcc[a[i]] != rightOcc[a[i]])) {↵
      return true;↵
    }↵
  }↵
  return false;↵
}↵

int main() {↵
#ifdef GOLIKOV↵
  assert(freopen("in", "rt", stdin));↵
  auto _clock_start = chrono::high_resolution_clock::now();↵
#endif↵
  ios::sync_with_stdio(false);↵
  cin.tie(nullptr);↵

  int t; cin >> t;↵
  while (t--) {↵
    cout << (solveTest() ? "Yes" : "No") << '\n';↵
  }↵

#ifdef GOLIKOV↵
  cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(↵
      chrono::high_resolution_clock::now()↵
          - _clock_start).count() << "ms." << endl;↵
#endif↵
  return 0;↵
}↵
~~~~~↵
</spoiler>↵

[problem:1819B]↵

Author: [user:Tikhon228,2023-04-16]↵

Preparation: [user:Kon567889,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819B]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
//#pragma GCC target("trapv")↵
#include <iostream>↵
#include <vector>↵
#include <algorithm>↵
#include <set>↵
#include <string>↵
#include <cmath>↵
#include <map>↵
#include <iostream>↵
#include <list>↵
#include <stack>↵
#include <cassert>↵
using namespace std;↵

typedef long long ll;↵
typedef long double ld;↵

#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);↵

const ll INF = 1e9 * 1e9 + 100, SZ = 1100;↵

ll n;↵
vector<pair<ll, ll>> vec;↵
map<ll, pair<ll, ll>> blocks;↵

pair<ll, ll> solve() {↵
set<pair<ll, ll>> widest, longest;↵

for (size_t i = 0; i < vec.size(); i++) {↵
widest.insert({ vec[i].first, i });↵
longest.insert({ vec[i].second, i });↵

blocks[i] = vec[i];↵
}↵

pair<ll, ll> ans = { -1, -1 };↵
bool mode = 0;↵
ll prevw = INF, prevh = INF, prv = -1;↵
bool cringe = 0;↵
while (widest.size() != 0) {↵
if (mode == 0) {↵
ll cur = (*widest.rbegin()).first, sum = 0;↵
if (ans.second == -1) ans.second = cur;↵
prv = blocks[(*widest.rbegin()).second].second;↵

while (widest.size() > 0 && (*widest.rbegin()).first == cur) {↵
auto it = (--widest.end());↵
longest.erase({blocks[it->second].second, it->second });↵
sum += blocks[it->second].second;↵
widest.erase(it);↵
}↵

if (!cringe) ans.first = sum;↵
prv = sum;↵
if (prevw == INF) {↵
prevh = cur;↵
} else {↵
prevw -= sum;↵
if (prevh != cur) return { -1, -1 };↵
}↵
} else {↵
ll cur = (*longest.rbegin()).first, sum = 0;↵
if (!cringe) {↵
ans.first = cur + prv;↵
cringe = 1;↵
}↵

while (longest.size() > 0 && (*longest.rbegin()).first == cur) {↵
auto it = (--longest.end());↵
widest.erase({ blocks[it->second].first, it->second });↵
sum += blocks[it->second].first;↵
longest.erase(it);↵
}↵

if (prevw == INF) {↵
prevw = cur;↵
prevh -= sum;↵
if (prevw != cur) return { -1, -1 };↵
} else {↵
prevh -= sum;↵
if (prevw != cur) return { -1, -1 };↵
}↵
}↵

mode ^= 1;↵
}↵

if (prevh == 0 || prevw == 0 || prevh == INF || prevw == INF) {↵
return ans;↵
} else {↵
return { -1, -1 };↵
}↵
}↵

signed main() {↵
fastInp;↵

    ll t;↵
    cin >> t;↵
    ↵
    while (t--) {↵
        vec.clear();↵
        blocks.clear();↵
     cin >> n;↵
    ↵
     vec.resize(n);↵
     for (auto& c : vec) cin >> c.first >> c.second;↵
    ↵
     vector<pair<ll, ll>> ans;↵
    ↵
     ans.push_back(solve());↵
     swap(ans.back().first, ans.back().second);↵
     if (ans.back().first == -1) ans.pop_back();↵
    ↵
     for (auto& c : vec) swap(c.first, c.second);↵
    ↵
     ans.push_back(solve());↵
     if (ans.back().first == -1) ans.pop_back();↵
    ↵
     if (ans.size() == 2 && ans[0] == ans[1]) {↵
     ans.pop_back();↵
     }↵
     cout << ans.size() << "\n";↵
    ↵
     for (auto c : ans) cout << c.first << " " << c.second << "\n";↵
    }↵
    ↵
return 0;↵
}↵
~~~~~↵
</spoiler>↵

[problem:1819C]↵

Author: [user:golikovnik,2023-04-16]↵

Preparation: [user:DishonoredRighteous,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819C]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
// #pragma comment(linker, "/stack:200000000")↵
// #pragma GCC optimize("Ofast,no-stack-protector")↵
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")↵
// #pragma GCC optimize("unroll-loops")↵

#include <stdio.h>↵
#include <bits/stdc++.h>↵

#ifdef PERVEEVM_LOCAL↵
    #define debug(x) std::cerr << (#x) << ":\t" << (x) << std::endl↵
#else↵
    #define debug(x) 238↵
#endif↵

#define fastIO std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0)↵
#define NAME "File"↵

using ll = long long;↵
using ld = long double;↵

#ifdef PERVEEVM_LOCAL↵
    std::mt19937 rnd(238);↵
#else↵
    std::mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());↵
#endif↵

template<typename T>↵
bool smin(T& a, const T& b) {↵
    if (b < a) {↵
        a = b;↵
        return true;↵
    }↵
    return false;↵
}↵

template<typename T>↵
bool smax(T& a, const T& b) {↵
    if (a < b) {↵
        a = b;↵
        return true;↵
    }↵
    return false;↵
}↵

const double PI = atan2(0.0, -1.0);↵
const int INF = 0x3f3f3f3f;↵
const ll LINF = (ll)2e18;↵
const int N = 200100;↵

std::vector<int> g[N];↵
int d[N], par[N];↵
bool onDiameter[N];↵

void dfs(int v, int p, int depth) {↵
d[v] = depth;↵
par[v] = p;↵

for (auto to : g[v]) {↵
if (to != p) {↵
dfs(to, v, depth + 1);↵
}↵
}↵
}↵

void run() {↵
int n;↵
scanf("%d", &n);↵

for (int i = 0; i < n - 1; ++i) {↵
int from, to;↵
scanf("%d%d", &from, &to);↵
g[from - 1].push_back(to - 1);↵
g[to - 1].push_back(from - 1);↵
}    ↵

dfs(0, 0, 0);↵
int v1 = 0;↵
for (int i = 0; i < n; ++i) {↵
if (d[i] > d[v1]) {↵
v1 = i;↵
}↵
}↵

dfs(v1, v1, 0);↵
int v2 = v1;↵
for (int i = 0; i < n; ++i) {↵
if (d[i] > d[v2]) {↵
v2 = i;↵
}↵
}↵

std::vector<int> diameter;↵
for (int v = v2; v != v1; v = par[v]) {↵
onDiameter[v] = true;↵
diameter.push_back(v);↵
}↵
onDiameter[v1] = true;↵
diameter.push_back(v1);↵
std::reverse(diameter.begin(), diameter.end());↵

for (int i = 0; i < n; ++i) {↵
if (onDiameter[i]) {↵
continue;↵
}↵
if (!onDiameter[par[i]]) {↵
printf("No\n");↵
return;↵
}↵
}↵

printf("Yes\n");↵
std::vector<int> ans;↵
for (int i = 0; i < (int)diameter.size(); i += 2) {↵
ans.push_back(diameter[i]);↵
if (i + 1 != (int)diameter.size()) {↵
for (auto to : g[diameter[i + 1]]) {↵
if (!onDiameter[to]) {↵
ans.push_back(to);↵
}↵
}↵
}↵
}↵

if (diameter.size() % 2 == 0) {↵
for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {↵
ans.push_back(diameter[i]);↵
if (i - 1 >= 0) {↵
for (auto to : g[diameter[i - 1]]) {↵
if (!onDiameter[to]) {↵
ans.push_back(to);↵
}↵
}↵
}↵
}↵
} else {↵
for (int i = (int)diameter.size() - 1; i > 0; i -= 2) {↵
ans.push_back(diameter[i - 1]);↵
if (i - 2 >= 0) {↵
for (auto to : g[diameter[i - 2]]) {↵
if (!onDiameter[to]) {↵
ans.push_back(to);↵
}↵
}↵
}↵
}↵
}↵

assert((int)ans.size() == n);↵
for (auto i : ans) {↵
printf("%d ", i + 1);↵
}↵
printf("\n");↵
}↵

int main(void) {↵
    // freopen(NAME".in", "r", stdin);↵
    // freopen(NAME".out", "w", stdout);↵

    #ifdef PERVEEVM_LOCAL↵
        auto start = std::chrono::high_resolution_clock::now();↵
    #endif↵

    run();↵

    #ifdef PERVEEVM_LOCAL↵
        auto end = std::chrono::high_resolution_clock::now();↵
        std::cerr << "Execution time: "↵
                  << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()↵
                  << " ms" << std::endl;↵
    #endif↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

[problem:1819D]↵

Author: [user:Um_nik,2023-04-16]↵

Preparation: [user:dshindov,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819D]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵

#include <exception>↵

using namespace std;↵
using ll = long long;↵

void solve() {↵
    int n, m;↵
    cin >> n >> m;↵
    vector<vector<int>> apples(n);↵
    for (int i = 0; i < n; ++i) {↵
        int k;↵
        cin >> k;↵
        for (int j = 0; j < k; ++j) {↵
            int x;↵
            cin >> x;↵
            apples[i].push_back(x);↵
        }↵
    }↵
    // vector<int> last(m + 1, -1);↵
    unordered_map<int, int> last;↵
    auto get_last = [&](int i) {↵
        if (!last.count(i)) {↵
            return -1;↵
        } else {↵
            return last[i];↵
        }↵
    };↵
    vector<char> can_zero(n + 1, false);↵
    vector<int> prev(n + 1, 0);↵
    can_zero[0] = true;↵
    int oops = -1;↵
    for (int i = 0; i < n; ++i) {↵
        if (apples[i].empty()) {↵
            can_zero[i + 1] = true;↵
            last[0] = i;↵
        } else {↵
            int nearest_pair = get_last(0);↵
            int new_oops = oops;↵
            for (int x : apples[i]) {↵
                nearest_pair = max(nearest_pair, get_last(x));↵
                new_oops = max(new_oops, get_last(x));↵
                last[x] = i;↵
            }↵
            if (nearest_pair != -1) {↵
                int nearest_zero = prev[nearest_pair];↵
                if (oops < nearest_zero) {↵
                    can_zero[i + 1] = true;↵
                }↵
            }↵
            oops = new_oops;↵
        }↵
        if (can_zero[i + 1]) {↵
            prev[i + 1] = i + 1;↵
        } else {↵
            prev[i + 1] = prev[i];↵
        }↵
    }↵
    // vector<char> used(m + 1, false);↵
    unordered_set<int> used;↵
    vector<int> max_cnt(n + 1, 0);↵
    int current_cnt = 0;↵
    for (int i = n - 1; i >= 0; --i) {↵
        bool fail = false;↵
        if (apples[i].empty()) {↵
            used.insert(0);↵
        }↵
        for (int x : apples[i]) {↵
            if (used.count(x)) {↵
                fail = true;↵
                break;↵
            }↵
            used.insert(x);↵
            ++current_cnt;↵
        }↵
        if (fail) {↵
            break;↵
        }↵
        if (used.count(0)) {↵
            max_cnt[i] = m;↵
        } else {↵
            max_cnt[i] = current_cnt;↵
        }↵
    }↵
    int ans = 0;↵
    for (int i = 0; i <= n; ++i) {↵
        if (can_zero[i]) {↵
            ans = max(ans, max_cnt[i]);↵
        }↵
    }↵
    cout << ans << '\n';↵
}↵

int main() {↵
    cin.tie(nullptr)->sync_with_stdio(false);↵
    int t = 1;↵
    cin >> t;↵
    while (t--) solve();↵
}↵
~~~~~↵
</spoiler>↵

[problem:1819E]↵

Author: [user:Tikhon228,2023-04-16]↵

Preparation: [user:grphil,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819E]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵

#define x first↵
#define y second↵

using namespace std;↵

mt19937 rnd;↵

struct solve {↵

vector<pair<int, int>> r;↵

vector<vector<pair<int, int>>> s;↵

vector<int> ans;↵

int n, m;↵

static constexpr int rep = 45;↵

int dfs(int a, int p, int b) {↵
for (auto i : s[a]) {↵
if (i.x == b) {↵
return i.y;↵
}↵
if (i.x == p) {↵
continue;↵
}↵

int x = dfs(i.x, a, b);↵

if (x != -1) {↵
return x;↵
}↵
}↵
return -1;↵
}↵

solve() {↵
cin >> n >> m;↵
r.resize(m);↵
for (int i = 0; i < m; i++) {↵
cin >> r[i].x >> r[i].y;↵
r[i].x--;↵
r[i].y--;↵
}↵

s.resize(n);↵
ans.resize(m, -1);↵
int cnt = 0;↵
for (int i = 0; i < m; i++) {↵
rem(i);↵
for (int j = 0; j < rep; j++) {↵
if (!ask_end(i)) {↵
ans[i] = 1;↵
break;↵
}↵
}↵
if (ans[i] == 1) {↵
add(i);↵
cnt++;↵
s[r[i].x].emplace_back(r[i].y, i);↵
s[r[i].y].emplace_back(r[i].x, i);↵
}↵
}↵

assert(cnt == n - 1);↵

for (int i = 0; i < m; i++) {↵
if (ans[i] != -1) continue;↵
ans[i] = 1;↵

int c = dfs(r[i].x, -1, r[i].y);↵
rem(c);↵
add(i);↵
for (int j = 0; j < rep; j++) {↵
if (!ask_end(i)) {↵
ans[i] = 0;↵
break;↵
}↵
}↵
rem(i);↵
add(c);↵
}↵
cout << "!";↵
for (int i = 0; i < m; i++) {↵
cout << ' ' << ans[i];↵
}↵
cout << endl;↵
int x;↵
cin >> x;↵
if (x != 1) {↵
exit(1);↵
}↵
}↵

void rem(int x) {↵
cout << "- " << x + 1 << endl;↵
}↵

void add(int x) {↵
cout << "+ " << x + 1 << endl;↵
}↵

bool ask(int a) {↵
cout << "? " << a + 1 << endl;↵
// cerr << "? " << a + 1 << endl;↵
int x;↵
cin >> x;↵
return x == 1;↵
}↵

bool ask_end(int i) {↵
// cerr << "ask_end " << i << endl;↵
int a = r[i].x;↵
if (rnd() % 2) {↵
a = r[i].y;↵
}↵
return ask(a);↵
}↵

};↵

int main() {↵
int t;↵
cin >> t;↵
for (int i = 0; i < t; i++) {↵
solve();↵
}↵
}↵
~~~~~↵
</spoiler>↵

[problem:1819F]↵

Author: [user:teraqqq,2023-04-16]↵

Preparation: [user:teraqqq,2023-04-16]↵

<spoiler summary="Editorial">↵
[tutorial:1819F]↵
</spoiler>↵

<spoiler summary="Solution">↵
~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵
using pi = pair<int, int>;↵
using ll = long long;↵

const int Q = 1e5;↵
const int N = 20;↵
const int V = N*Q;↵

const ll LINF = 1e18;↵

struct MinMaxValue {↵
    ll min_value;↵
    ll max_value;↵

    MinMaxValue operator * (const MinMaxValue& x) const {↵
        if (x.max_value < 0 || max_value < 0) {↵
            return MinMaxValue { 0, -1 };↵
        }↵

        return MinMaxValue {↵
            .min_value = x.min_value + min_value,↵
            .max_value = x.max_value + max_value↵
        };↵
    }↵

    MinMaxValue operator + (const MinMaxValue& x) const {↵
        if (x.max_value == -1) return *this;↵
        if (max_value == -1) return x;↵

        return MinMaxValue {↵
            .min_value = min(x.min_value, min_value),↵
            .max_value = max(x.max_value, max_value)↵
        };↵
    }↵

    MinMaxValue& operator += (const MinMaxValue& x) {↵
        return *this = *this + x;↵
    }↵

    void Reset() {↵
        min_value = 0;↵
        max_value = -1;↵
    }↵
};↵

struct {↵
    MinMaxValue dig, ver, hor;↵
    int cnt;↵
    int go[4];↵
} nd[V];↵
int vc = 0;↵
MinMaxValue dig[N+1], ver[N+1], hor[N+1];↵

std::set<ll> words;↵

int NewVertex(int h) {↵
    int* go = nd[vc].go;↵
    go[0] = go[1] = go[2] = go[3] = -1;↵
    nd[vc].dig = dig[h];↵
    nd[vc].hor = hor[h];↵
    nd[vc].ver = ver[h];↵
    nd[vc].cnt = 0;↵
    return vc++;↵
}↵

tuple<const MinMaxValue&, const MinMaxValue&, const MinMaxValue&, int> GetState(int v, int h) {↵
    return v == -1 ? make_tuple(cref(dig[h]), cref(ver[h]), cref(hor[h]), 0)↵
                   : make_tuple(cref(nd[v].dig), cref(nd[v].ver), cref(nd[v].hor), nd[v].cnt);↵
}↵

void Calculate(int v, int h, int corner) {↵
    auto [dig0, ver0, hor0, cnt0] = GetState(nd[v].go[corner^0], h-1);↵
    auto [dig1, ver1, hor1, cnt1] = GetState(nd[v].go[corner^1], h-1);↵
    auto [dig2, ver2, hor2, cnt2] = GetState(nd[v].go[corner^2], h-1);↵
    auto [dig3, ver3, hor3, cnt3] = GetState(nd[v].go[corner^3], h-1);↵

    nd[v].cnt = cnt0 + cnt1 + cnt2 + cnt3;↵

    nd[v].dig.Reset();↵
    if (cnt0 == 0) nd[v].dig += hor2 * dig3 * ver1;↵
    if (cnt3 == 0) nd[v].dig += ver2 * dig0 * hor1;↵

    nd[v].hor = ver0 * dig2 * dig3 * ver1;↵
    if (cnt2 + cnt3 == 0) nd[v].hor += hor0 * hor1;↵

    nd[v].ver = hor0 * dig1 * dig3 * hor2;↵
    if (cnt1 + cnt3 == 0) nd[v].ver += ver0 * ver2;↵
}↵

void UpdateCount(int v, int h, int corner, ll msk, ll msk_save) {↵
    if (h == 0) {↵
        if (nd[v].cnt == 0) {↵
            words.insert(msk_save);↵
        } else {↵
            words.erase(msk_save);↵
        }↵
        nd[v].cnt ^= 1;↵
    } else {↵
        UpdateCount(nd[v].go[msk & 3], h-1, msk & 3, msk >> 2, msk_save);↵
        Calculate(v, h, corner);↵
    }↵
}↵

bool near_symbols[256][256];↵

MinMaxValue GetAnswer(int h) {↵
    int v = 0;↵

    if (nd[v].cnt == 0) {↵
        return MinMaxValue { .min_value = 2, .max_value = 4 * dig[h-1].max_value };↵
    }↵

    MinMaxValue res; res.Reset();↵

    bool cycle_len2 = false;↵
    if (nd[v].cnt <= 1) cycle_len2 = true;↵
    if (nd[v].cnt == 2) {↵
        string s, t;↵

        for (ll msk =       *words.begin(); s.size() < h; msk >>= 2) s.push_back("abdc"[msk & 3]);↵
        for (ll msk = *next(words.begin()); t.size() < h; msk >>= 2) t.push_back("abdc"[msk & 3]);↵
        auto flag = near_symbols[s.back()][t.back()];↵

        if (s.substr(0, h-1) == t.substr(0, h-1) && flag) {↵
            cycle_len2 = true;↵
        }↵

        int s_suf = 0, t_suf = 0;↵
        while (s_suf < h && s[h - s_suf - 1] == s.back()) ++s_suf;↵
        while (t_suf < h && t[h - t_suf - 1] == t.back()) ++t_suf;↵

        if (s_suf == t_suf && s_suf < h && flag && s.substr(0, h-s_suf-1) == t.substr(0, h-t_suf-1)↵
                && s.back() == t[h - s_suf - 1]↵
                && t.back() == s[h - t_suf - 1]) cycle_len2 = true;↵
    }↵

    if (cycle_len2) {↵
        res.min_value = 2;↵
        res.max_value = 2;↵
    }↵

    while (h != 0) {↵
        const int v0 = nd[v].go[0], v1 = nd[v].go[1], v2 = nd[v].go[2], v3 = nd[v].go[3];↵
        const auto& dig0 = get<0>(GetState(v0, h-1));↵
        const auto& dig1 = get<0>(GetState(v1, h-1));↵
        const auto& dig2 = get<0>(GetState(v2, h-1));↵
        const auto& dig3 = get<0>(GetState(v3, h-1));↵

        if(dig0.max_value > 0 && dig1.max_value > 0 && dig2.max_value > 0 && dig3.max_value > 0) {↵
            res += dig0 * dig1 * dig2 * dig3;↵
        }↵

        --h;↵
        if (v0 != -1 && nd[v0].cnt == nd[v].cnt) { v = v0; continue; }↵
        if (v1 != -1 && nd[v1].cnt == nd[v].cnt) { v = v1; continue; }↵
        if (v2 != -1 && nd[v2].cnt == nd[v].cnt) { v = v2; continue; }↵
        if (v3 != -1 && nd[v3].cnt == nd[v].cnt) { v = v3; continue; }↵
        break;↵
    }↵
    return res;↵
}↵

int main() {↵
    ios::sync_with_stdio(0); cin.tie(0);↵

    int n, q; cin >> n >> q;↵
    vector<ll> v(q);↵

    for (int i = 0; i < 4; ++i) {↵
        int j = (i + 1) % 4;↵
        near_symbols['a' + i]['a' + j] = true;↵
        near_symbols['a' + j]['a' + i] = true;↵
    }↵

    dig[0] = ver[0] = hor[0] = { 1, 1 };↵
    for (int i = 1; i <= n; ++i) {↵
        dig[i] = hor[i-1] * dig[i-1] * ver[i-1];↵
        hor[i] = ver[i] = hor[i-1] * hor[i-1] + ver[i-1] * ver[i-1] * dig[i-1] * dig[i-1];↵
    }↵

    int m_root = NewVertex(n); // make_root↵
    assert(m_root == 0);↵

    for (int i = 0; i < q; ++i) {↵
        string s; cin >> s;↵
        for (int j = 0; j < n; ++j) {↵
            v[i] += (s[j] == 'b' || s[j] == 'c' ? 1ll : 0) << (2*j);↵
            v[i] += (s[j] == 'c' || s[j] == 'd' ? 2ll : 0) << (2*j);↵
        }↵

        int w = 0;↵
        for (int j = 0; j < n; ++j) {↵
            int& next = nd[w].go[(v[i] >> (2*j)) & 3];↵
            if (next == -1) next = NewVertex(n-j-1);↵
            w = next;↵
        }↵
    }↵

    for (ll msk : v) {↵
        UpdateCount(0, n, 0, msk, msk);↵
        auto [a, b] = GetAnswer(n);↵

        if (a > b) {↵
            cout << -1 << '\n';↵
        } else {↵
            cout << a << " " << b << '\n';↵
        }↵
    }↵
}↵
~~~~~

</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский DishonoredRighteous 2023-04-17 22:29:29 22873
en1 Английский DishonoredRighteous 2023-04-16 15:47:34 1394 Initial revision (published)