Submission #35052

#	Time	Username	Problem	Language	Result	Execution time	Memory
35052		model_code	Longest beautiful sequence (IZhO17_subsequence)	C++11	0 / 100	0 ms	3588 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 a[100100];
int prv[100100];
int k[100100];
int mx[100100];
int cnt[(1<<10) + 10];
int last[(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 cur = 0;
		int ind = 0;
		for(int mask = 0; mask < (1<<10); mask++){
			int K = cnt[mask & x];
			if(K != k[i]) continue;
			if(last[mask] == 0) continue;
			int cc = last[mask];
			if(mx[cc] > cur){
				cur = mx[cc];
				ind = cc;
			}
		}
		cur++;
		mx[i] = cur;
		prv[i] = ind;
		if(last[x] == 0 || mx[last[x]] < cur) last[x] = 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;
    //scanf("%d", &t);
    for(int i=1; i <= t; i++){
      //printf("Case #%d\n", i);
      solve();
    }

    return 0;
}

Compilation message (stderr)

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

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