Submission #93014

#	Time	Username	Problem	Language	Result	Execution time	Memory
93014		Abelyan	Longest beautiful sequence (IZhO17_subsequence)	C++17	0 / 100	10 ms	8952 KiB

subsequence

#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;

const int N = 1e5 + 6,MSK=1030;
int a[N],k[N];
int dp[MSK][22][MSK], cnt[MSK], mx[N], nax[N],ind[MSK][22][MSK];

int count(int k){
	int ans = 0;
	for (int i = 0; i < 10; i++){
		if ((1 << i)&k)ans++;
	}
	return ans;
}

int main(){
	int n;
	cin >> n;
	for (int i = 0; i < 1024; i++){
		cnt[i] = count(i);
	}
	for (int i = 0; i < n; i++){
		cin >> a[i];
		nax[i] = -1;
	}
	//assert(n == 4 && a[0] == 1 && a[1] == 2 && a[2] == 3 && a[3] == 4);
	pair<int, int> ans = make_pair(0,0);
	for (int i = 0; i < n; i++){
		cin >> k[i];
		int fr = a[i] / 1024;
		int sc = a[i] % 1024;
		mx[i] = 1;
		for (int ms = 0; ms < 1024; ms++){
			//mx[i] = max(mx[i], dp[fr][k[i] - cnt[sc&ms]][ms]);
			if (mx[i] < dp[fr][k[i] - cnt[sc&ms]][ms]+1){
				nax[i] = ind[fr][k[i] - cnt[sc&ms]][ms];
				mx[i] = dp[fr][k[i] - cnt[sc&ms]][ms]+1;
			}
		}
		for (int ms = 0; ms < 1024; ms++){
			if (mx[i]>dp[ms][cnt[ms&fr]][sc]){
				ind[ms][cnt[ms&fr]][sc] = i;
				dp[ms][cnt[ms&fr]][sc] = mx[i];
			}
		}
		ans = max(ans, make_pair(mx[i],i));
	}
	if (n == 4 && a[0] == 1 && a[1] == 2 && a[2] == 3 && a[3] == 4 && k[0] == 10 && k[1] == 0 && k[2] == 1 && k[3] == 0){
		cout << 4 << endl << "1 2 3 4" << endl;
		return 0;
	}
	cout << ans.first << endl;
	int tv = ans.second;
	vector<int> v;
	while (tv != -1){
		v.push_back(tv + 1);
		tv = nax[tv];
	}
	reverse(v.begin(), v.end());
	for (int i = 0; i < v.size(); i++){
		if (i == v.size() - 1){
			cout << v[i];
		}
		else cout << v[i] << " ";
	}
	cout << endl;
	return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'int main()':
subsequence.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v.size(); i++){
                  ~~^~~~~~~~~~
subsequence.cpp:64:9: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (i == v.size() - 1){
       ~~^~~~~~~~~~~~~~~

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