oj.uz

Submission #515618

# Submission time Handle Problem Language Result Execution time Memory
515618 2022-01-19T10:48:10 Z kshitij_sodani Present (RMI21_present) C++14
100 / 100
 3093 ms 32268 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<=bb+cc;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 3017 ms 32164 KB Output is correct
2 Correct 3030 ms 32164 KB Output is correct
3 Correct 3022 ms 32160 KB Output is correct
4 Correct 2873 ms 32104 KB Output is correct
5 Correct 2989 ms 32176 KB Output is correct
6 Correct 3093 ms 32164 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3017 ms 32164 KB Output is correct
2 Correct 3030 ms 32164 KB Output is correct
3 Correct 3022 ms 32160 KB Output is correct
4 Correct 2873 ms 32104 KB Output is correct
5 Correct 2989 ms 32176 KB Output is correct
6 Correct 3093 ms 32164 KB Output is correct
7 Correct 3074 ms 32184 KB Output is correct
8 Correct 3003 ms 32160 KB Output is correct
9 Correct 2964 ms 32140 KB Output is correct
10 Correct 2883 ms 32164 KB Output is correct
11 Correct 2857 ms 32200 KB Output is correct
12 Correct 2888 ms 32160 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3017 ms 32164 KB Output is correct
2 Correct 3030 ms 32164 KB Output is correct
3 Correct 3022 ms 32160 KB Output is correct
4 Correct 2873 ms 32104 KB Output is correct
5 Correct 2989 ms 32176 KB Output is correct
6 Correct 3093 ms 32164 KB Output is correct
7 Correct 3074 ms 32184 KB Output is correct
8 Correct 3003 ms 32160 KB Output is correct
9 Correct 2964 ms 32140 KB Output is correct
10 Correct 2883 ms 32164 KB Output is correct
11 Correct 2857 ms 32200 KB Output is correct
12 Correct 2888 ms 32160 KB Output is correct
13 Correct 3029 ms 32164 KB Output is correct
14 Correct 2886 ms 32160 KB Output is correct
15 Correct 2880 ms 32196 KB Output is correct
16 Correct 2857 ms 32164 KB Output is correct
17 Correct 2861 ms 32164 KB Output is correct
18 Correct 2862 ms 32164 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3017 ms 32164 KB Output is correct
2 Correct 3030 ms 32164 KB Output is correct
3 Correct 3022 ms 32160 KB Output is correct
4 Correct 2873 ms 32104 KB Output is correct
5 Correct 2989 ms 32176 KB Output is correct
6 Correct 3093 ms 32164 KB Output is correct
7 Correct 3074 ms 32184 KB Output is correct
8 Correct 3003 ms 32160 KB Output is correct
9 Correct 2964 ms 32140 KB Output is correct
10 Correct 2883 ms 32164 KB Output is correct
11 Correct 2857 ms 32200 KB Output is correct
12 Correct 2888 ms 32160 KB Output is correct
13 Correct 3029 ms 32164 KB Output is correct
14 Correct 2886 ms 32160 KB Output is correct
15 Correct 2880 ms 32196 KB Output is correct
16 Correct 2857 ms 32164 KB Output is correct
17 Correct 2861 ms 32164 KB Output is correct
18 Correct 2862 ms 32164 KB Output is correct
19 Correct 2935 ms 32168 KB Output is correct
20 Correct 2878 ms 32160 KB Output is correct
21 Correct 2863 ms 32168 KB Output is correct
22 Correct 2913 ms 32220 KB Output is correct
23 Correct 2813 ms 32168 KB Output is correct
24 Correct 2906 ms 32164 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3017 ms 32164 KB Output is correct
2 Correct 3030 ms 32164 KB Output is correct
3 Correct 3022 ms 32160 KB Output is correct
4 Correct 2873 ms 32104 KB Output is correct
5 Correct 2989 ms 32176 KB Output is correct
6 Correct 3093 ms 32164 KB Output is correct
7 Correct 3074 ms 32184 KB Output is correct
8 Correct 3003 ms 32160 KB Output is correct
9 Correct 2964 ms 32140 KB Output is correct
10 Correct 2883 ms 32164 KB Output is correct
11 Correct 2857 ms 32200 KB Output is correct
12 Correct 2888 ms 32160 KB Output is correct
13 Correct 3029 ms 32164 KB Output is correct
14 Correct 2886 ms 32160 KB Output is correct
15 Correct 2880 ms 32196 KB Output is correct
16 Correct 2857 ms 32164 KB Output is correct
17 Correct 2861 ms 32164 KB Output is correct
18 Correct 2862 ms 32164 KB Output is correct
19 Correct 2935 ms 32168 KB Output is correct
20 Correct 2878 ms 32160 KB Output is correct
21 Correct 2863 ms 32168 KB Output is correct
22 Correct 2913 ms 32220 KB Output is correct
23 Correct 2813 ms 32168 KB Output is correct
24 Correct 2906 ms 32164 KB Output is correct
25 Correct 2904 ms 32164 KB Output is correct
26 Correct 2949 ms 32164 KB Output is correct
27 Correct 2940 ms 32268 KB Output is correct
28 Correct 2936 ms 32168 KB Output is correct
29 Correct 3084 ms 32164 KB Output is correct
30 Correct 2913 ms 32168 KB Output is correct