oj.uz

Submission #515614

# Submission time Handle Problem Language Result Execution time Memory
515614 2022-01-19T10:45:04 Z kshitij_sodani Present (RMI21_present) C++14
70 / 100
 3144 ms 32244 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--){
		int 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));
				}
			}
			
			int 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 3028 ms 32168 KB Output is correct
2 Correct 3144 ms 32164 KB Output is correct
3 Correct 3038 ms 32164 KB Output is correct
4 Correct 2990 ms 32244 KB Output is correct
5 Correct 3073 ms 32164 KB Output is correct
6 Correct 3004 ms 32160 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3028 ms 32168 KB Output is correct
2 Correct 3144 ms 32164 KB Output is correct
3 Correct 3038 ms 32164 KB Output is correct
4 Correct 2990 ms 32244 KB Output is correct
5 Correct 3073 ms 32164 KB Output is correct
6 Correct 3004 ms 32160 KB Output is correct
7 Correct 2998 ms 32164 KB Output is correct
8 Correct 2938 ms 32060 KB Output is correct
9 Correct 3004 ms 32164 KB Output is correct
10 Correct 3045 ms 32040 KB Output is correct
11 Correct 3047 ms 32160 KB Output is correct
12 Correct 3008 ms 32164 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3028 ms 32168 KB Output is correct
2 Correct 3144 ms 32164 KB Output is correct
3 Correct 3038 ms 32164 KB Output is correct
4 Correct 2990 ms 32244 KB Output is correct
5 Correct 3073 ms 32164 KB Output is correct
6 Correct 3004 ms 32160 KB Output is correct
7 Correct 2998 ms 32164 KB Output is correct
8 Correct 2938 ms 32060 KB Output is correct
9 Correct 3004 ms 32164 KB Output is correct
10 Correct 3045 ms 32040 KB Output is correct
11 Correct 3047 ms 32160 KB Output is correct
12 Correct 3008 ms 32164 KB Output is correct
13 Correct 3036 ms 32164 KB Output is correct
14 Correct 3015 ms 32200 KB Output is correct
15 Correct 3071 ms 32164 KB Output is correct
16 Correct 3007 ms 32160 KB Output is correct
17 Correct 2990 ms 32188 KB Output is correct
18 Correct 3006 ms 32168 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3028 ms 32168 KB Output is correct
2 Correct 3144 ms 32164 KB Output is correct
3 Correct 3038 ms 32164 KB Output is correct
4 Correct 2990 ms 32244 KB Output is correct
5 Correct 3073 ms 32164 KB Output is correct
6 Correct 3004 ms 32160 KB Output is correct
7 Correct 2998 ms 32164 KB Output is correct
8 Correct 2938 ms 32060 KB Output is correct
9 Correct 3004 ms 32164 KB Output is correct
10 Correct 3045 ms 32040 KB Output is correct
11 Correct 3047 ms 32160 KB Output is correct
12 Correct 3008 ms 32164 KB Output is correct
13 Correct 3036 ms 32164 KB Output is correct
14 Correct 3015 ms 32200 KB Output is correct
15 Correct 3071 ms 32164 KB Output is correct
16 Correct 3007 ms 32160 KB Output is correct
17 Correct 2990 ms 32188 KB Output is correct
18 Correct 3006 ms 32168 KB Output is correct
19 Correct 2949 ms 32168 KB Output is correct
20 Incorrect 3033 ms 32196 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3028 ms 32168 KB Output is correct
2 Correct 3144 ms 32164 KB Output is correct
3 Correct 3038 ms 32164 KB Output is correct
4 Correct 2990 ms 32244 KB Output is correct
5 Correct 3073 ms 32164 KB Output is correct
6 Correct 3004 ms 32160 KB Output is correct
7 Correct 2998 ms 32164 KB Output is correct
8 Correct 2938 ms 32060 KB Output is correct
9 Correct 3004 ms 32164 KB Output is correct
10 Correct 3045 ms 32040 KB Output is correct
11 Correct 3047 ms 32160 KB Output is correct
12 Correct 3008 ms 32164 KB Output is correct
13 Correct 3036 ms 32164 KB Output is correct
14 Correct 3015 ms 32200 KB Output is correct
15 Correct 3071 ms 32164 KB Output is correct
16 Correct 3007 ms 32160 KB Output is correct
17 Correct 2990 ms 32188 KB Output is correct
18 Correct 3006 ms 32168 KB Output is correct
19 Correct 2949 ms 32168 KB Output is correct
20 Incorrect 3033 ms 32196 KB Output isn't correct
21 Halted 0 ms 0 KB -