Submission #761473

#	Time	Username	Problem	Language	Result	Execution time	Memory
761473		US3RN4M3	Present (RMI21_present)	C++17	29 / 100	740 ms	74832 KiB

Main

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

const int mx = 23;

const int mask = (1 << mx) - 1;

int deltas[1 << mx];

vector<int> rules[mx];
const int mx3 = 40;
int g[mx3][mx3];

bool check(int i) {
	for(int a = 1; a < mx; a++) if((i >> a) & 1) for(int b = a + 1; b < mx; b++) if((i >> b) & 1) {
		if(!((i >> g[a][b]) & 1)) return false;
	}
	return true;
}

bool check2(ll i) {
	for(int a = 1; a < mx3; a++) if((i >> a) & 1) for(int b = mx; b < mx3; b++) if((i >> b) & 1) {
		if(!((i >> g[a][b]) & 1)) return false;
	}
	return true;
}
const int mx2 = 1000001;
int valid[mx2];

vector<int> vf(int i) {
	vector<int> res;
	for(int b = 0; b < 30; b++) {
		if((i >> b) & 1) res.push_back(b);
	}
	return res;
}
main() {
	int prev = 0;
	for(int i = 0; i < mx3; i++) for(int j = 0; j < mx3; j++) {
		g[i][j] = __gcd(i, j);
	}
	deltas[mask - 1] = 2;
	int x = 0;
	for(int i = 2; i <= mask - 1; i += 2) {
		if(check(i)) {
			x++;
			deltas[prev] = i - prev;
			prev = i;
		}
	}
	int cnt = 1;
	ll cur = 0;
	valid[0] = 0;
	while(cnt < mx2) {
		do {
			cur += deltas[cur & mask];
		} while(!check2(cur));
		valid[cnt++] = cur;
	}
	int t; cin >> t;
	for(int i = 0; i < t; i++) {
		ll q; cin >> q;
		vector<int> a = vf(valid[q]);
		cout << a.size() << " ";
		for(int j : a) cout << j << " ";
		cout << endl;
	}
	/*
	cout << valid[mx2 - 1] << endl;
	for(int i = 1; i <= 30; i++) if((valid[mx2 - 1] >> i) & 1) cout << i << " ";
	cout << "done" << endl;*/
}

Compilation message (stderr)

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

• Subtask 1: 8 / 8
• Subtask 2: 21 / 21
• Subtask 3: 0 / 41
• Subtask 4: 0 / 14
• Subtask 5: 0 / 16