oj.uz

Submission #515611

# Submission time Handle Problem Language Result Execution time Memory
515611 2022-01-19T10:41:44 Z kshitij_sodani Present (RMI21_present) C++14
70 / 100
 3110 ms 58792 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;
	//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<<bb);j++){
			vector<int> tt;
			int cur=0;
			int ec=0;
			for(int i=0;i<bb;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<=2*bb;i++){
			vis3[i]=0;
		}

		for(int ii=2*bb;ii>=1;ii--){
			vis3[ii]=-1;
			int ac=0;
			int bc=0;
			for(int j=2*bb;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=2*bb-1;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<<bb);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:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for(int k=0;k+1<tt.size();k++){
      |                ~~~^~~~~~~~~~
Main.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |    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:31:6: warning: unused variable 'oo' [-Wunused-variable]
   31 |  int oo=0;
      |      ^~
Main.cpp:32:6: warning: unused variable 'pp' [-Wunused-variable]
   32 |  int pp=0;
      |      ^~
Main.cpp:60:7: warning: unused variable 'val5' [-Wunused-variable]
   60 |   int val5=0;
      |       ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2814 ms 29088 KB Output is correct
2 Correct 2791 ms 29092 KB Output is correct
3 Correct 2875 ms 29092 KB Output is correct
4 Correct 2785 ms 29092 KB Output is correct
5 Correct 2859 ms 29192 KB Output is correct
6 Correct 2836 ms 29132 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2814 ms 29088 KB Output is correct
2 Correct 2791 ms 29092 KB Output is correct
3 Correct 2875 ms 29092 KB Output is correct
4 Correct 2785 ms 29092 KB Output is correct
5 Correct 2859 ms 29192 KB Output is correct
6 Correct 2836 ms 29132 KB Output is correct
7 Correct 2866 ms 28996 KB Output is correct
8 Correct 2831 ms 29088 KB Output is correct
9 Correct 2895 ms 29136 KB Output is correct
10 Correct 2903 ms 29092 KB Output is correct
11 Correct 2996 ms 29088 KB Output is correct
12 Correct 3110 ms 29088 KB Output is correct

Subtask #3
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2814 ms 29088 KB Output is correct
2 Correct 2791 ms 29092 KB Output is correct
3 Correct 2875 ms 29092 KB Output is correct
4 Correct 2785 ms 29092 KB Output is correct
5 Correct 2859 ms 29192 KB Output is correct
6 Correct 2836 ms 29132 KB Output is correct
7 Correct 2866 ms 28996 KB Output is correct
8 Correct 2831 ms 29088 KB Output is correct
9 Correct 2895 ms 29136 KB Output is correct
10 Correct 2903 ms 29092 KB Output is correct
11 Correct 2996 ms 29088 KB Output is correct
12 Correct 3110 ms 29088 KB Output is correct
13 Correct 2820 ms 29088 KB Output is correct
14 Correct 2852 ms 29108 KB Output is correct
15 Correct 2854 ms 29104 KB Output is correct
16 Correct 2875 ms 29124 KB Output is correct
17 Correct 2876 ms 29188 KB Output is correct
18 Correct 2833 ms 29092 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2814 ms 29088 KB Output is correct
2 Correct 2791 ms 29092 KB Output is correct
3 Correct 2875 ms 29092 KB Output is correct
4 Correct 2785 ms 29092 KB Output is correct
5 Correct 2859 ms 29192 KB Output is correct
6 Correct 2836 ms 29132 KB Output is correct
7 Correct 2866 ms 28996 KB Output is correct
8 Correct 2831 ms 29088 KB Output is correct
9 Correct 2895 ms 29136 KB Output is correct
10 Correct 2903 ms 29092 KB Output is correct
11 Correct 2996 ms 29088 KB Output is correct
12 Correct 3110 ms 29088 KB Output is correct
13 Correct 2820 ms 29088 KB Output is correct
14 Correct 2852 ms 29108 KB Output is correct
15 Correct 2854 ms 29104 KB Output is correct
16 Correct 2875 ms 29124 KB Output is correct
17 Correct 2876 ms 29188 KB Output is correct
18 Correct 2833 ms 29092 KB Output is correct
19 Correct 2833 ms 29096 KB Output is correct
20 Runtime error 1761 ms 58792 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2814 ms 29088 KB Output is correct
2 Correct 2791 ms 29092 KB Output is correct
3 Correct 2875 ms 29092 KB Output is correct
4 Correct 2785 ms 29092 KB Output is correct
5 Correct 2859 ms 29192 KB Output is correct
6 Correct 2836 ms 29132 KB Output is correct
7 Correct 2866 ms 28996 KB Output is correct
8 Correct 2831 ms 29088 KB Output is correct
9 Correct 2895 ms 29136 KB Output is correct
10 Correct 2903 ms 29092 KB Output is correct
11 Correct 2996 ms 29088 KB Output is correct
12 Correct 3110 ms 29088 KB Output is correct
13 Correct 2820 ms 29088 KB Output is correct
14 Correct 2852 ms 29108 KB Output is correct
15 Correct 2854 ms 29104 KB Output is correct
16 Correct 2875 ms 29124 KB Output is correct
17 Correct 2876 ms 29188 KB Output is correct
18 Correct 2833 ms 29092 KB Output is correct
19 Correct 2833 ms 29096 KB Output is correct
20 Runtime error 1761 ms 58792 KB Execution killed with signal 6
21 Halted 0 ms 0 KB -