Submission #605633

#	Time	Username	Problem	Language	Result	Execution time	Memory
605633		tonfai_nokhong	Longest beautiful sequence (IZhO17_subsequence)	C++17	100 / 100	2168 ms	56380 KiB

subsequence

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <ctime>
 
#define pb push_back
#define ll long long
#define mp make_pair
#define f first
#define s second
#define pii pair < int, int >
#define ull unsigned long long
#define pll pair < ll, ll >
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it ++)
#define all(s) s.begin(), s.end()
#define sz(a) (int)a.size()
 
const int inf = (1ll << 30) - 1;
const int maxn = (int) 1e5 + 10;
 
using namespace std;
 
int dp[(1<<20)+ 10][10 + 3];
int a[100100];
int prv[100100];
int k[100100];
int mx[100100];
int cnt[(1<<10) + 10];
int n;
void solve(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	for(int i = 1; i <= n; i++){
		scanf("%d", &k[i]);
	}
	for(int i = 0; i < (1<<10); i++)
		cnt[i] = __builtin_popcount(i);
 
	for(int i = 1; i <= n; ++i){
		int x = a[i] & ((1<<10)-1);
		int y = (a[i] >> 10) & ((1<<10)-1);
		int &cur = mx[i];
		int &ind = prv[i];
		for(int mask = 0; mask < (1<<10); mask++){
			int K = k[i] - cnt[mask & y];
			if(K < 0 || K > 10) continue;
			int &cc = dp[(mask<<10)|x][K];
			if(mx[cc] > cur){
				cur = mx[cc];
				ind = cc;
			}
		}
		cur++;
		
		for(int mask = 0; mask < (1<<10); ++mask){
			int K = cnt[mask & x];
			int &cc = dp[(y<<10)|mask][K];
			if(mx[cc] < cur){
				cc = i;
			}
		}
	}
	int j = 0;
	for(int i = 1; i <= n; i++){
		if(mx[j] < mx[i]){
			j = i;
		}
	}
	vector<int> ans;
	while(j){
		ans.pb(j);
		j = prv[j];
	}
	reverse(all(ans));
	printf("%d\n", ans.size());
	for(int i = 0; i < ans.size(); i++){
		if(i) printf(" ");
		printf("%d", ans[i]);
	}
	printf("\n");
}
 
int main () {
    int t=1;
    for(int i=1; i <= t; i++){
      solve();
    }

    return 0;
}

Compilation message (stderr)

subsequence.cpp: In function 'void solve()':
subsequence.cpp:84:11: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
   84 |  printf("%d\n", ans.size());
      |          ~^     ~~~~~~~~~~
      |           |             |
      |           int           std::vector<int>::size_type {aka long unsigned int}
      |          %ld
subsequence.cpp:85:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for(int i = 0; i < ans.size(); i++){
      |                 ~~^~~~~~~~~~~~
subsequence.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
subsequence.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
subsequence.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |   scanf("%d", &k[i]);
      |   ~~~~~^~~~~~~~~~~~~

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