Submission #1052491

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052491		coolsentenceidontremember	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	1735 ms	97068 KiB

subsequence

#include<bits/stdc++.h>

#pragma GCC optimize("O3", "unroll-loops")


#define ll long long
#define ld long double
#define ff first
#define ss second
#define db double
#define time_begin() auto begin = chrono::high_resolution_clock::now()
#define time_end() auto end = chrono::high_resolution_clock::now(); auto elapsed = chrono::duration_cast<chrono::nanoseconds>(end-begin); auto sec = elapsed.count() * 1e-9; cerr << "\n\nExecution time: " << sec << " seconds";
#define check_time() cerr << "\nStatus : "; if (sec>1) cerr << "Time Limit Exceeded 1!!!1!111"; else cerr << "You good brother"

using namespace std;

void setIO(string s = ""){
 ios_base::sync_with_stdio(false);
 cin.tie(nullptr);
 cout.tie(nullptr);
 if (!s.empty()){
	freopen((s+".in").c_str(), "r", stdin);
	freopen((s+".out").c_str(), "w", stdout);
	}
}

const int split = 10;
const int N = 1e5;
struct state{
	int len;
	int end;
} dp[1<<split][1<<split][split+1];

int bc[1<<split][1<<split];

int a[N], k[N], trace[N];

int main(){
	for (int i = 0; i < (1<<split); i++) for (int j = 0; j < (1<<split); j++) bc[i][j] = __builtin_popcount(i&j);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) cin >> k[i];
	iota(trace, trace+n, 0);
	int ans = 1, best = 0;
	for (int i = 0; i < n; i++){
		int l = a[i]>>split, r = a[i]%(1<<split);
		int lbs = 1;
		for (int l_prev = 0; l_prev < (1<<split); l_prev++){
			int bit = k[i] - bc[l_prev][l];
			if (bit < 0 || bit > split) continue;
			int comp = dp[l_prev][r][bit].len + 1;
			if (comp > lbs){
				lbs = comp;
				trace[i] = dp[l_prev][r][bit].end;
			} 
		}
		if (lbs > ans){
			ans = lbs;
			best = i;
		}
		for (int spread = 0; spread < (1<<split); spread++){
			state &s = dp[l][spread][bc[r][spread]];
			if (lbs > s.len){
				s.len = lbs;
				s.end = i;
			}
		}
	}
	cout << ans << '\n';
	vector<int> lbs;
	while (trace[best]!=best){
		lbs.push_back(best);
		best = trace[best];
	}
	lbs.push_back(best);
	reverse(lbs.begin(), lbs.end());
	for (const int &i : lbs) cout << i+1 << ' ';
}

Compilation message (stderr)

subsequence.cpp: In function 'void setIO(std::string)':
subsequence.cpp:22:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  freopen((s+".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
subsequence.cpp:23:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  freopen((s+".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 16 / 16
• Subtask 3: 17 / 17
• Subtask 4: 60 / 60