Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #ifdef ONPC
- # define _GLIBCXX_DEBUG
- #define deb(a) cerr << "yo " << #a << " = " << a << endl;
- #else
- #define deb(a)
- #endif
- #include <bits/stdc++.h>
- #define endl "\n"
- //#pragma GCC optimize("Ofast")
- //#pragma GCC target("avx,avx2,fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- ll MOD = 998244353;
- ll INF = 1e18;
- #define int ll
- const int N = 600000;
- int t[N*4];
- int nn,s=1;
- vector<ll> pp;
- void build(){
- nn = pp.size();
- while(s<nn)s*=2;
- for (int i = s; i < 2 * s; i++) t[i] = INF;
- for (int i = s; i < s + nn; i++) t[i] = pp[i - s];
- for(int i=s;--i;)t[i]=min(t[i+i], t[i+i+1]);
- }
- //void add(int i,int val){for(t[i+=s]+=val;i/=2;)t[i]=t[i+i]+t[i+i+1];}
- int get(int l,int r){//[l..r]
- int res=INF;
- for(l+=s,r+=s+1;l<r;l/=2,r/=2){
- if(l&1)res = min(res,t[l++]);
- if(r&1)res = min(res,t[--r]);
- }
- return res;
- }
- vector<vector<ll> > pl;
- vector<ll> p;
- vector<ll> us;
- set<pair<ll, ll> > st;
- ll gv = 1;
- void ad(ll l, ll r){ // [l; r]
- if (!gv)
- return;
- auto l1 = st.lower_bound({l, r});
- //cout << l << " suk " << r << endl;
- if ((*l1).first > r){
- l1--;
- if ((*l1).second < l){
- st.insert({l, r});
- }
- else{
- gv = 0;
- }
- } else{
- gv = 0;
- }
- if (!gv) return;
- //cout << gv << endl;
- //cout << pl[p[l]][0] << " " << pl[p[l]][1] << " " << pl[p[l]][2] << "\n";
- us[pl[p[l]][0]] = us[pl[p[l]][1]] = us[pl[p[r]][2]] = 2;
- us[l]--;
- us[r]--;
- for (int i = l + 1; i < r; i++){
- if (!us[pl[p[i]][0]] && pl[p[i]][0] == i && pl[p[i]][1] > r){
- ad(pl[p[i]][1], pl[p[i]][2]);
- }
- else {
- if (!us[pl[p[i]][0]] && pl[p[i]][2] == i && pl[p[i]][1] < l) {
- ad(pl[p[i]][0], pl[p[i]][1]);
- }
- else{
- //cout << "suka";
- gv = 0;
- }
- }
- us[i] = 1;
- }
- }
- ll go(vector<ll> a){
- //cout << 234324;
- gv = 1;
- st.insert({-1, -1});
- st.insert({INF, INF});
- ll ans = 0;
- ll n = a.size();
- us.resize(n, 0);
- for (int i = 0; i < n; i++) us[i] = 0;
- p = a;
- ll r =0;
- for (int i = 1; i < n; i++){
- if (a[i] == 1){
- r = i;
- break;
- }
- }
- pl.clear();
- pl.resize(n / 3 + 1);
- for (int i = 0; i < n; i++){
- pl[a[i]].push_back(i);
- }
- vector<ll> nxt(n);
- vector<ll> lst(n, INF);
- for (int i = n - 1; i > -1; i--){
- nxt[i] = lst[a[i]];
- lst[a[i]] = i;
- }
- pp = nxt;
- build();
- ad(0, r);
- //cout << gv << endl;
- for (int i = 1; i <= n / 3; i++){
- if (!us[pl[i][0]] && get(pl[i][0], pl[i][1]) < pl[i][1]){
- ad(pl[i][1], pl[i][2]);
- }
- if (!us[pl[i][0]] && get(pl[i][1], pl[i][2]) < pl[i][2]){
- ad(pl[i][0], pl[i][1]);
- }
- }
- //cout << gv << endl;
- ans = 1;
- {
- for (int i = 0; i < n; i++) {
- cout << p[i] << " ";
- }
- cout << endl;
- for (int i = 0; i < n; i++) {
- cout << us[i] << " ";
- }
- cout << endl;
- }
- cout << "gv " << gv << endl;
- for (int i = 0; i < n;){
- if (!us[i]){
- //cout << i << " " << gv << endl;
- if (i >= n - 2){
- gv = 0;
- break;
- }
- vector<ll> nx;
- ll lst = 0;
- for (int j = i; j < n; j++){
- if (us[j] == 0){
- nx.push_back(j);
- }
- if (us[j] == 1){
- break;
- }
- lst = j;
- if (nx.size() == 6){
- break;
- }
- }
- lst++;
- if (nx.size() != 3 && nx.size() != 6){
- //cout << "suka";
- gv = 0;
- break;
- }
- if (nx.size() == 3) {
- if (p[nx[0]] == p[nx[1]] && p[nx[1]] == p[nx[2]]) {
- ans *= 2;
- ans %= MOD;
- i = lst;
- }
- else{
- gv = 0;
- break;
- }
- }
- else{
- if (p[nx[0]] == p[nx[2]] && p[nx[2]] == p[nx[4]] && p[nx[1]] == p[nx[3]] && p[nx[3]] == p[nx[5]]){
- i = lst;
- }
- else{
- if (p[nx[0]] == p[nx[1]] && p[nx[1]] == p[nx[2]] && p[nx[3]] == p[nx[4]] && p[nx[4]] == p[nx[5]]) {
- ans *= 4;
- ans %= MOD;
- i = lst;
- }
- else{
- gv = 0;
- break;
- }
- }
- }
- }
- else{
- i++;
- }
- }
- st.clear();
- cout << ans << endl;
- cout << gv << endl;
- return ans * gv;
- }
- signed main() {
- ios::sync_with_stdio(0), cin.tie(0), cout.tie(0), cout << fixed << setprecision(20);
- ll n;
- cin >> n;
- vector<ll> b(3 * n);
- vector<ll> a(3 * n);
- for (int i = 0; i < 3 * n; i++){
- cin >> b[i];
- }
- ll fl = 0;
- ll sd = 0;
- for (int i = 0; i < 3 * n; i++){
- if (b[i] == 1){
- fl++;
- }
- if (fl == 1){
- sd = i;
- break;
- }
- }
- for (int i = 0; i < 3 * n; i++){
- a[i] = b[(i + sd) % (3 * n)];
- }
- ll ans = 0;
- ans += go(a);
- fl = 0;
- sd = 0;
- for (int i = 0; i < 3 * n; i++){
- if (b[i] == 1){
- fl++;
- }
- if (fl == 2){
- sd = i;
- break;
- }
- }
- for (int i = 0; i < 3 * n; i++){
- a[i] = b[(i + sd) % (3 * n)];
- }
- ans += go(a);
- fl = 0;
- sd = 0;
- for (int i = 0; i < 3 * n; i++){
- if (b[i] == 1){
- fl++;
- }
- if (fl == 3){
- sd = i;
- break;
- }
- }
- for (int i = 0; i < 3 * n; i++){
- a[i] = b[(i + sd) % (3 * n)];
- }
- ans += go(a);
- ans %= MOD;
- cout << ans;
- #ifdef ONPC
- // cerr << endl << "finished in " << clock() * 1.0 / CLOCKS_PER_SEC << " sec" << endl;
- #endif
- }
- //egor lox
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement