Submission #502194

#	Time	Username	Problem	Language	Result	Execution time	Memory
502194		tmn2005	Longest beautiful sequence (IZhO17_subsequence)	C++17	7 / 100	3 ms	460 KiB

subsequence

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

#define ar array
#define fr first
#define sc second

#define vec vector
#define ret return

#define ins insert
#define mk make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front

#define int long long

#define pii pair<int,int>

#define all(s) s.begin(), s.end()
#define allr(s) s.rbegin(), s.rend()

#define NeedForSpeed ios::sync_with_stdio(0),cin.tie(0);
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const int N=1e6+12,INF=1e9,mod = 1e9+7;
bool iswowel(char n){ n = toupper(n); if(n == 'A' || n == 'O' || n == 'U' || n == 'E' || n == 'I') return true; else return false;}
int n, m, k, x, y, l, r, o, ans, res, ok, mx, mn = INF;
int a[N], b[N], dp[N], pr[N];
vec<int>s;

void print(int v){
	if(v != pr[v])print(pr[v]);
	s.pb(v);
}
main(){
	NeedForSpeed
	//freopen("subsequence.in", "r", stdin);
	//freopen("subsequence.out", "w", stdout);
    cin>>n;
    for(int i=0; i<n; i++)cin>>a[i];
    for(int i=0; i<n; i++)cin>>b[i];
    
	for(int mask=(1<<n)-1; mask>=0; mask--){
		int l = 0, ok = 1, old = -1;
		set<int>v;
		for(int i=0; i<n; i++){
			if(mask & (1<<i)){
				l++;
				if(l == 1){
					old = i;
					v.ins(i);
					continue;
				}	
				if(__builtin_popcount(a[old] & a[i]) != b[i]){
					ok = 0;
					break;
				}
				v.ins(i);
				old = i;
			}
		}
		if(ok){
			//cout<<mask<<" "<<__builtin_popcount(mask)<<endl;
			if(__builtin_popcount(mask) > ans){
				ans = __builtin_popcount(mask);
				res = mask;
			}
		}
	}
	cout<<__builtin_popcount(res)<<endl;
	for(int i=0; i<n; i++){
		if(res & (1<<i))cout<<i+1<<" ";
	}



	return 0;
}

Compilation message (stderr)

subsequence.cpp:39:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 | main(){
      | ^~~~

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