Submission #1350826

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350826		AzeTurk810	Sequence (APIO23_sequence)	C++17	0 / 100	23 ms	6208 KiB

sequence

/*
Telebe of Adicto && Mamedov yani AzeTurk810
I see humans but no humanity
*/
#include "sequence.h"
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <set>
#include <utility>
#include <vector>

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

using ll = long long;
using namespace std;

#define ln '\n'
#define INFi 1e9
#define INFll 1e18

#ifdef ONPC
#include <algo.hpp>
#else
#define dbg(...)
#define dbg_out(...)
#define assert(...)
#endif

int _n, ans;
vector<int> A;
map<int, vector<int>> ind;

inline void systemd() {
    ans = 1;
    for (size_t i = 0; i < _n; i++) {
        ind[A[i]].push_back(i);
    }
}

int W(int l, int r, int x) {
    auto itl = lower_bound(ind[x].begin(), ind[x].end(), l);
    auto itr = upper_bound(ind[x].begin(), ind[x].end(), r);
    itr--;
    return itr - itl + 1;
}

int W(int l, int r, set<int> st) {
    int res = 0;
    for (int x : st) {
        dbg(make_pair(l, r));
        dbg(x);
        res = max(res, W(l, r, x));
        dbg(res);
    }
    return res;
}

char solve() {
    systemd();
    for (size_t i = 0; i < _n; i++) {
        multiset<int> mst;
        mst.insert(A[i]);
        auto it1 = mst.begin(), it2 = mst.begin();
        for (size_t j = i + 1; j < _n; j++) {
            mst.insert(A[j]);
            set<int> st;
            dbg(mst);
            dbg(*it1);
            dbg(*it2);
            dbg(*(++it1));
            it1--;
            dbg(i);
            dbg(j);
            if (A[j] >= *it2) {
                if (it1 != it2)
                    it1++;
                else 
                    it2++;
                goto nxt;
            } 
            if (A[j] >= *it1) {
                if (it1 != it2) {
                    it1++;
                    it2--;
                    assert(it1 == it2);
                } else {
                    it1++;
                }
                goto nxt;
            }
            if (it1 != it2) {
                it2--;
            } else {
                it1--;
            }
nxt:
            dbg(*it1);
            dbg(*it2);
            assert(*it1 <= *it2);
            if (mst.size() & 1) {
                assert(it1 == it2);
            }
            st.insert(*it1);
            st.insert(*it2);
            ans = max(ans, W(i, j, st));
        }
    }
    return 0;
}

int sequence(int N, std::vector<int> _a) {
    _n = N;
    A = _a;
    assert(!solve());
    return ans;
}

// Attack on titan<3

// Just Imaginary
/*
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄
⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈
⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀
⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀
⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
7
1 2 3 1 2 1 3

14
2 6 2 5 3 4 2 1 4 3 5 6 3 2

9
1 1 2 3 4 3 2 1 1
*/

Compilation message (stderr)

sequence.cpp:28: warning: "assert" redefined
   28 | #define assert(...)
      | 
In file included from /usr/include/c++/13/cassert:44,
                 from sequence.cpp:7:
/usr/include/assert.h:102: note: this is the location of the previous definition
  102 | #  define assert(expr)                                                  \
      |

• Subtask 1: 0 / 11
• Subtask 2: 0 / 17
• Subtask 3: 0 / 7
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 22
• Subtask 7: 0 / 18