Submission #502735

#TimeUsernameProblemLanguageResultExecution timeMemory
502735tox1c_kidLongest beautiful sequence (IZhO17_subsequence)C++17
Compilation error
0 ms0 KiB
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native") // Enable AVX/AVX2 #pragma GCC optimize("Ofast") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("unswitch-loops") #pragma GCC optimize("fast-math") #pragma GCC optimize("rename-registers") // Optimization flags #include <iostream> #include <iomanip> #include <fstream> #include <cstdio> #include <sstream> #include <cassert> #include <vector> #include <numeric> #include <string> #include <bitset> #include <cmath> #include <complex> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <random> #include <chrono> #include <ctime> #include <ext/pb_ds/detail/standard_policies.hpp> #include <ext/pb_ds/assoc_container.hpp> /* ⠄⠄⠄⢰⣧⣼⣯⠄⣸⣠⣶⣶⣦⣾⠄⠄⠄⠄⡀⠄⢀⣿⣿⠄⠄⠄⢸⡇⠄⠄ ⠄⠄⠄⣾⣿⠿⠿⠶⠿⢿⣿⣿⣿⣿⣦⣤⣄⢀⡅⢠⣾⣛⡉⠄⠄⠄⠸⢀⣿⠄ ⠄⠄⢀⡋⣡⣴⣶⣶⡀⠄⠄⠙⢿⣿⣿⣿⣿⣿⣴⣿⣿⣿⢃⣤⣄⣀⣥⣿⣿⠄ ⠄⠄⢸⣇⠻⣿⣿⣿⣧⣀⢀⣠⡌⢻⣿⣿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⣿⣿⣿⠄ ⠄⢀⢸⣿⣷⣤⣤⣤⣬⣙⣛⢿⣿⣿⣿⣿⣿⣿⡿⣿⣿⡍⠄⠄⢀⣤⣄⠉⠋⣰ ⠄⣼⣖⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣿⣿⢇⣿⣿⡷⠶⠶⢿⣿⣿⠇⢀⣤ ⠘⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣽⣿⣿⣿⡇⣿⣿⣿⣿⣿⣿⣷⣶⣥⣴⣿⡗ ⢀⠈⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠄ ⢸⣿⣦⣌⣛⣻⣿⣿⣧⠙⠛⠛⡭⠅⠒⠦⠭⣭⡻⣿⣿⣿⣿⣿⣿⣿⣿⡿⠃⠄ ⠘⣿⣿⣿⣿⣿⣿⣿⣿⡆⠄⠄⠄⠄⠄⠄⠄⠄⠹⠈⢋⣽⣿⣿⣿⣿⣵⣾⠃⠄ ⠄⠘⣿⣿⣿⣿⣿⣿⣿⣿⠄⣴⣿⣶⣄⠄⣴⣶⠄⢀⣾⣿⣿⣿⣿⣿⣿⠃⠄⠄ ⠄⠄⠈⠻⣿⣿⣿⣿⣿⣿⡄⢻⣿⣿⣿⠄⣿⣿⡀⣾⣿⣿⣿⣿⣛⠛⠁⠄⠄⠄ ⠄⠄⠄⠄⠈⠛⢿⣿⣿⣿⠁⠞⢿⣿⣿⡄⢿⣿⡇⣸⣿⣿⠿⠛⠁⠄⠄⠄⠄⠄ ⠄⠄⠄⠄⠄⠄⠄⠉⠻⣿⣿⣾⣦⡙⠻⣷⣾⣿⠃⠿⠋⠁⠄⠄⠄⠄⠄⢀⣠⣴ ⣿⣿⣿⣶⣶⣮⣥⣒⠲⢮⣝⡿⣿⣿⡆⣿⡿⠃⠄⠄⠄⠄⠄⠄⠄⣠⣴⣿⣿⣿ */ using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef double db; typedef unsigned long long ull; typedef pair<ll, ll> pll; typedef pair<int, int> pii; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define all(x) (x).begin(), (x).end() mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); template <typename A, typename B> string to_string(pair<A, B> p); template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p); template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p); string to_string(const string& s) { return '"' + s + '"'; } string to_string(const char* s) { return to_string((string) s); } string to_string(vector<bool> v) { bool first = true; string res = "{"; for (int i = 0; i < static_cast<int>(v.size()); i++) { if (!first) { res += ", "; } first = false; res += to_string(v[i]); } res += "}"; return res; } template <typename A> string to_string(A v) { bool first = true; string res = "{"; for (const auto &x : v) { if (!first) { res += ", "; } first = false; res += to_string(x); } res += "}"; return res; } template <typename A, typename B> string to_string(pair<A, B> p) { return "(" + to_string(p.first) + ", " + to_string(p.second) + ")"; } template <typename A, typename B, typename C> string to_string(tuple<A, B, C> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")"; } template <typename A, typename B, typename C, typename D> string to_string(tuple<A, B, C, D> p) { return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")"; } void debug_out() { cout << "\n"; } template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cout << " " << to_string(H); debug_out(T...); } #ifdef CLOWN #define dbg(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__); #else #define dbg(...); #endif int test = 0; void fastio() { ios_base::sync_with_stdio(false); cin.tie(nullptr); } void solve() { int n; cin >> n; vector<int> dp(n); vector<int> a(n); vector<int> k(n); for (int i =0 ; i < n; i++) cin >> a[i]; for (int j = 0; j < n; j++) cin >> k[j]; vector<int> p(n, -1); int id = 0, mx = 0; vector<int> used(256 + 1, -1); dbg(dp) if (n <= 5000) { for (int i = 0; i < n; i++) { // now dp[i] = 1; for (int j = 0; j < i; j++) { // prev if (__builtin_popcount(a[i] & a[j]) != k[i]) continue; if (dp[i] < dp[j] + 1) { dp[i] = dp[j] + 1; p[i] = j; } } if (dp[i] > mx) { mx = dp[i]; id = i; } } vector<int> ans; while (id != -1) { ans.push_back(id); id = p[id]; } reverse(all(ans)); cout << ans.size() << "\n"; for (auto i : ans) { cout << i + 1 << " "; } } else { for (int i = 0; i < n; i++) { // now dp[i] = 1; used[a[i]] = 0; if (i == 0) continue; for (int j = 0; j <= (1 << 8); j++) { // prev if (__builtin_popcount(a[i] & j) == k[i] && used[j] != -1) { if (dp[i] < dp[used[j]] + 1) { dp[i] = dp[used[j]] + 1; p[i] = used[j]; } } if (dp[i] > dp[used[a[i]]]) { used[a[i]] = i; } } } for (int i = 0; i < n; i++) { if (dp[i] > mx) { mx = dp[i]; id = i; } } vector<int> ans; while (id != -1) { ans.push_back(id); id = p[id]; } reverse(all(ans)); cout << ans.size() << "\n"; for (auto i : ans) cout << i + 1 << " "; } } int32_t main() { #ifdef CLOWN freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int t = 1; fastio(); if (test) cin >> t; while (t--) { solve(); } return 0; }

Compilation message (stderr)

In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/gthr.h:148,
                 from /usr/include/c++/10/ext/atomicity.h:35,
                 from /usr/include/c++/10/bits/ios_base.h:39,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from subsequence.cpp:9:
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:102:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:103:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:104:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:106:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:107:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:108:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:109:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:110:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:112:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:114:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:116:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:117:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:119:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  121 | __gthrw(pthread_mutex_unlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:121:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  122 | __gthrw(pthread_mutex_init)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:122:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  123 | __gthrw(pthread_mutex_destroy)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:123:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  125 | __gthrw(pthread_cond_init)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:125:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  126 | __gthrw(pthread_cond_broadcast)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:126:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  127 | __gthrw(pthread_cond_signal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:127:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  128 | __gthrw(pthread_cond_wait)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:128:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  129 | __gthrw(pthread_cond_timedwait)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:129:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  130 | __gthrw(pthread_cond_destroy)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:130:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  132 | __gthrw(pthread_key_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:132:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  133 | __gthrw(pthread_key_delete)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:133:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  134 | __gthrw(pthread_mutexattr_init)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:134:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  135 | __gthrw(pthread_mutexattr_settype)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:135:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
  136 | __gthrw(pthread_mutexattr_destroy)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:136:1: error: attribute value 'tune=native' was already specified in 'target' attribute
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute
  237 | __gthrw2(__gthrw_(__pthread_key_create),
      |          ^~~~~~~~
/usr/include/x86_64-linux-gnu/c++/10/bits/gthr-default.h:237:10: error: attribute value 'tune=native' was already specified in 'target' attribute