oj.uz

Submission #761473

# Submission time Handle Problem Language Result Execution time Memory
761473 2023-06-19T18:46:03 Z US3RN4M3 Present (RMI21_present) C++17
29 / 100
 740 ms 74832 KB 
#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

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

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 37036 KB Output is correct
2 Correct 715 ms 37100 KB Output is correct
3 Correct 725 ms 36936 KB Output is correct
4 Correct 716 ms 36980 KB Output is correct
5 Correct 732 ms 37028 KB Output is correct
6 Correct 722 ms 37032 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 37036 KB Output is correct
2 Correct 715 ms 37100 KB Output is correct
3 Correct 725 ms 36936 KB Output is correct
4 Correct 716 ms 36980 KB Output is correct
5 Correct 732 ms 37028 KB Output is correct
6 Correct 722 ms 37032 KB Output is correct
7 Correct 730 ms 37032 KB Output is correct
8 Correct 724 ms 37016 KB Output is correct
9 Correct 718 ms 36972 KB Output is correct
10 Correct 715 ms 36940 KB Output is correct
11 Correct 716 ms 37064 KB Output is correct
12 Correct 710 ms 37004 KB Output is correct

Subtask #3
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 37036 KB Output is correct
2 Correct 715 ms 37100 KB Output is correct
3 Correct 725 ms 36936 KB Output is correct
4 Correct 716 ms 36980 KB Output is correct
5 Correct 732 ms 37028 KB Output is correct
6 Correct 722 ms 37032 KB Output is correct
7 Correct 730 ms 37032 KB Output is correct
8 Correct 724 ms 37016 KB Output is correct
9 Correct 718 ms 36972 KB Output is correct
10 Correct 715 ms 36940 KB Output is correct
11 Correct 716 ms 37064 KB Output is correct
12 Correct 710 ms 37004 KB Output is correct
13 Runtime error 740 ms 74832 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 37036 KB Output is correct
2 Correct 715 ms 37100 KB Output is correct
3 Correct 725 ms 36936 KB Output is correct
4 Correct 716 ms 36980 KB Output is correct
5 Correct 732 ms 37028 KB Output is correct
6 Correct 722 ms 37032 KB Output is correct
7 Correct 730 ms 37032 KB Output is correct
8 Correct 724 ms 37016 KB Output is correct
9 Correct 718 ms 36972 KB Output is correct
10 Correct 715 ms 36940 KB Output is correct
11 Correct 716 ms 37064 KB Output is correct
12 Correct 710 ms 37004 KB Output is correct
13 Runtime error 740 ms 74832 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 720 ms 37036 KB Output is correct
2 Correct 715 ms 37100 KB Output is correct
3 Correct 725 ms 36936 KB Output is correct
4 Correct 716 ms 36980 KB Output is correct
5 Correct 732 ms 37028 KB Output is correct
6 Correct 722 ms 37032 KB Output is correct
7 Correct 730 ms 37032 KB Output is correct
8 Correct 724 ms 37016 KB Output is correct
9 Correct 718 ms 36972 KB Output is correct
10 Correct 715 ms 36940 KB Output is correct
11 Correct 716 ms 37064 KB Output is correct
12 Correct 710 ms 37004 KB Output is correct
13 Runtime error 740 ms 74832 KB Execution killed with signal 11
14 Halted 0 ms 0 KB -