oj.uz

Submission #515616

# Submission time Handle Problem Language Result Execution time Memory
515616 2022-01-19T10:47:33 Z kshitij_sodani Present (RMI21_present) C++14
70 / 100
 3144 ms 32168 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'

int pre[61][61];
int dp[1<<22][23];;
int cal[1<<22];
int cal2[1<<22];
int comp[1<<22];
int vis[1<<22];
int vis2[1<<22];
int vis3[44];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	for(int i=1;i<=60;i++){
		for(int j=1;j<=60;j++){
			pre[i][j]=__gcd(i,j);
		}
	}
	int zz=0;
	int zz2=0;
	int bb=18;
	int cc=19;
	//for(int i=1;i<=bb;i++){
	int oo=0;
	int pp=0;
		for(int j=0;j<(1<<(bb));j++){

			vector<int> tt;
			int cur=0;
			int ec=-1;
			for(int i=0;i<bb;i++){
				if((1<<i)&j){
					ec=(1<<i);
					tt.pb(i*2+2);
				}
			}
			if(tt.size()){
				cur=cal2[j-ec];
			}
			for(int k=0;k+1<tt.size();k++){
				cur|=(1<<((pre[tt[k]][tt.back()]/2)-1));
			}
			cal2[j]=cur;
			if((cur|j)==j){
			//	dp[(1<<bb)-j-1][0]=1;
				vis[j]=1;
				//oo++;
			}
//			pp++;

		}
	//	cout<<11<<endl;
		int val5=0;
		/*for(int j=0;j<(1<<bb);j++){
			for(int i=0;i<bb;i++){

			}
		}*/
		for(int j=0;j<(1<<cc);j++){
			vector<int> tt;
			int cur=0;
			int ec=0;
			for(int i=0;i<cc;i++){
				if((1<<i)&j){
					ec=(1<<i);
					tt.pb(i*2+1);
				}
			}
			if(tt.size()){
				cur=cal[j-ec];
			}
			for(int k=0;k+1<tt.size();k++){
				cur|=(1<<(pre[tt[k]][tt.back()]/2));
			}
			if((cur|j)==j){
				int su=0;
				for(int i=0;i<bb;i++){
					int st=1;
					for(auto k:tt){
						if((1<<(pre[k][2*i+2]/2))&j){

						}
						else{
							st=0;
							break;
						}
					}
					if(st==1){
						su+=(1<<i);
					}
				}
				vis2[j]=1;
				comp[j]=su;
				//cout<<j<<":"<<su<<endl;
			}

			cal[j]=cur;
			/*if(j>0){
				nn[j]+=nn[j-1];
			}*/
		}
	int t;
	cin>>t;
	while(t--){
		llo n;
		cin>>n;

		if(n==0){
			cout<<0<<endl;
			continue;
		}
		n++;
		for(int i=1;i<=bb+cc;i++){
			vis3[i]=0;
		}

		for(int ii=bb+cc;ii>=1;ii--){
			vis3[ii]=-1;
			int ac=0;
			int bc=0;
			for(int j=bb+cc-1;j>=ii;j-=2){
				if(vis3[j]==-1){
					ac+=(1<<((j-1)/2));
				}
				else{
					bc+=(1<<((j-1)/2));
				}
			}
			int ac2=0;
			int bc2=0;
			for(int j=bb+cc;j>=ii;j-=2){
				if(vis3[j]==-1){
					ac2+=(1<<(j/2));
				}
				else{
					bc2+=(1<<(j/2));
				}
			}
			
			llo zz=0;
			for(int j=0;j<(1<<bb);j++){
				dp[j][0]=0;
				if(vis[j]){
					if((j&ac)==0){
						if((j|bc)==j){
							dp[j][0]=1;
						}
					}
				}
				
				for(int i=1;i<=bb;i++){
					if((1<<(i-1))&j){
						dp[j][i]=dp[j][i-1]+dp[j-(1<<(i-1))][i-1];
					}
					else{
						dp[j][i]=dp[j][i-1];
					}
				}
			}
			for(int j=0;j<(1<<cc);j++){
				if(vis2[j]==1){
					if((j&ac2)>0){
						continue;
					}
					if((j|bc2)==j){
						zz+=dp[comp[j]][bb];
						
					}
				}
			}
			/*if(ii==1){
				cout<<zz<<"::"<<endl;
			}*/
			
			if(zz<n){
				n-=zz;
				vis3[ii]=1;
				continue;
			}

		}
		assert(n==1);
		vector<int> ans;
		for(int i=1;i<=2*bb;i++){
			if(vis3[i]==1){
				ans.pb(i);
			}
		}
		cout<<ans.size()<<" ";
		for(auto j:ans){
			cout<<j<<" ";
		}
		cout<<endl;
	}
	/*cout<<zz<<endl;
	cout<<zz2<<endl;
	int su=0;
	int cot=1500000000;
	cot=1e6;
	for(int i=1;i<=50;i++){
		int cur=max(i-(i/3)-1,(int)0);
		su+=(1LL<<cur);
		if(su>=cot){
			cout<<i<<endl;
			break;
		}
	}
*/




 
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:48:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    for(int k=0;k+1<tt.size();k++){
      |                ~~~^~~~~~~~~~
Main.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |    for(int k=0;k+1<tt.size();k++){
      |                ~~~^~~~~~~~~~
Main.cpp:27:6: warning: unused variable 'zz' [-Wunused-variable]
   27 |  int zz=0;
      |      ^~
Main.cpp:28:6: warning: unused variable 'zz2' [-Wunused-variable]
   28 |  int zz2=0;
      |      ^~~
Main.cpp:32:6: warning: unused variable 'oo' [-Wunused-variable]
   32 |  int oo=0;
      |      ^~
Main.cpp:33:6: warning: unused variable 'pp' [-Wunused-variable]
   33 |  int pp=0;
      |      ^~
Main.cpp:61:7: warning: unused variable 'val5' [-Wunused-variable]
   61 |   int val5=0;
      |       ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2885 ms 32164 KB Output is correct
2 Correct 3038 ms 32168 KB Output is correct
3 Correct 2880 ms 32160 KB Output is correct
4 Correct 2887 ms 32168 KB Output is correct
5 Correct 2813 ms 32168 KB Output is correct
6 Correct 2823 ms 32164 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2885 ms 32164 KB Output is correct
2 Correct 3038 ms 32168 KB Output is correct
3 Correct 2880 ms 32160 KB Output is correct
4 Correct 2887 ms 32168 KB Output is correct
5 Correct 2813 ms 32168 KB Output is correct
6 Correct 2823 ms 32164 KB Output is correct
7 Correct 2806 ms 32168 KB Output is correct
8 Correct 2937 ms 32164 KB Output is correct
9 Correct 2990 ms 32168 KB Output is correct
10 Correct 3044 ms 32164 KB Output is correct
11 Correct 2867 ms 32056 KB Output is correct
12 Correct 2910 ms 32168 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2885 ms 32164 KB Output is correct
2 Correct 3038 ms 32168 KB Output is correct
3 Correct 2880 ms 32160 KB Output is correct
4 Correct 2887 ms 32168 KB Output is correct
5 Correct 2813 ms 32168 KB Output is correct
6 Correct 2823 ms 32164 KB Output is correct
7 Correct 2806 ms 32168 KB Output is correct
8 Correct 2937 ms 32164 KB Output is correct
9 Correct 2990 ms 32168 KB Output is correct
10 Correct 3044 ms 32164 KB Output is correct
11 Correct 2867 ms 32056 KB Output is correct
12 Correct 2910 ms 32168 KB Output is correct
13 Correct 3042 ms 32164 KB Output is correct
14 Correct 3051 ms 32164 KB Output is correct
15 Correct 2996 ms 32168 KB Output is correct
16 Correct 3144 ms 32164 KB Output is correct
17 Correct 3086 ms 32160 KB Output is correct
18 Correct 3097 ms 32160 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2885 ms 32164 KB Output is correct
2 Correct 3038 ms 32168 KB Output is correct
3 Correct 2880 ms 32160 KB Output is correct
4 Correct 2887 ms 32168 KB Output is correct
5 Correct 2813 ms 32168 KB Output is correct
6 Correct 2823 ms 32164 KB Output is correct
7 Correct 2806 ms 32168 KB Output is correct
8 Correct 2937 ms 32164 KB Output is correct
9 Correct 2990 ms 32168 KB Output is correct
10 Correct 3044 ms 32164 KB Output is correct
11 Correct 2867 ms 32056 KB Output is correct
12 Correct 2910 ms 32168 KB Output is correct
13 Correct 3042 ms 32164 KB Output is correct
14 Correct 3051 ms 32164 KB Output is correct
15 Correct 2996 ms 32168 KB Output is correct
16 Correct 3144 ms 32164 KB Output is correct
17 Correct 3086 ms 32160 KB Output is correct
18 Correct 3097 ms 32160 KB Output is correct
19 Correct 2984 ms 32164 KB Output is correct
20 Incorrect 3029 ms 32160 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2885 ms 32164 KB Output is correct
2 Correct 3038 ms 32168 KB Output is correct
3 Correct 2880 ms 32160 KB Output is correct
4 Correct 2887 ms 32168 KB Output is correct
5 Correct 2813 ms 32168 KB Output is correct
6 Correct 2823 ms 32164 KB Output is correct
7 Correct 2806 ms 32168 KB Output is correct
8 Correct 2937 ms 32164 KB Output is correct
9 Correct 2990 ms 32168 KB Output is correct
10 Correct 3044 ms 32164 KB Output is correct
11 Correct 2867 ms 32056 KB Output is correct
12 Correct 2910 ms 32168 KB Output is correct
13 Correct 3042 ms 32164 KB Output is correct
14 Correct 3051 ms 32164 KB Output is correct
15 Correct 2996 ms 32168 KB Output is correct
16 Correct 3144 ms 32164 KB Output is correct
17 Correct 3086 ms 32160 KB Output is correct
18 Correct 3097 ms 32160 KB Output is correct
19 Correct 2984 ms 32164 KB Output is correct
20 Incorrect 3029 ms 32160 KB Output isn't correct
21 Halted 0 ms 0 KB -