oj.uz

답안 #515624

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
515624 2022-01-19T10:55:05 Z kshitij_sodani Present (RMI21_present) C++14
100 / 100
 3126 ms 32264 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2888 ms 32168 KB Output is correct
2 Correct 2876 ms 32172 KB Output is correct
3 Correct 2872 ms 32200 KB Output is correct
4 Correct 2922 ms 32164 KB Output is correct
5 Correct 2893 ms 32164 KB Output is correct
6 Correct 2989 ms 32164 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2888 ms 32168 KB Output is correct
2 Correct 2876 ms 32172 KB Output is correct
3 Correct 2872 ms 32200 KB Output is correct
4 Correct 2922 ms 32164 KB Output is correct
5 Correct 2893 ms 32164 KB Output is correct
6 Correct 2989 ms 32164 KB Output is correct
7 Correct 2972 ms 32164 KB Output is correct
8 Correct 2912 ms 32160 KB Output is correct
9 Correct 3126 ms 32164 KB Output is correct
10 Correct 2939 ms 32164 KB Output is correct
11 Correct 2841 ms 32160 KB Output is correct
12 Correct 2963 ms 32164 KB Output is correct

Subtask #3
41.0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2888 ms 32168 KB Output is correct
2 Correct 2876 ms 32172 KB Output is correct
3 Correct 2872 ms 32200 KB Output is correct
4 Correct 2922 ms 32164 KB Output is correct
5 Correct 2893 ms 32164 KB Output is correct
6 Correct 2989 ms 32164 KB Output is correct
7 Correct 2972 ms 32164 KB Output is correct
8 Correct 2912 ms 32160 KB Output is correct
9 Correct 3126 ms 32164 KB Output is correct
10 Correct 2939 ms 32164 KB Output is correct
11 Correct 2841 ms 32160 KB Output is correct
12 Correct 2963 ms 32164 KB Output is correct
13 Correct 2966 ms 32160 KB Output is correct
14 Correct 2887 ms 32160 KB Output is correct
15 Correct 2925 ms 32168 KB Output is correct
16 Correct 2909 ms 32164 KB Output is correct
17 Correct 2917 ms 32160 KB Output is correct
18 Correct 3004 ms 32164 KB Output is correct

Subtask #4
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2888 ms 32168 KB Output is correct
2 Correct 2876 ms 32172 KB Output is correct
3 Correct 2872 ms 32200 KB Output is correct
4 Correct 2922 ms 32164 KB Output is correct
5 Correct 2893 ms 32164 KB Output is correct
6 Correct 2989 ms 32164 KB Output is correct
7 Correct 2972 ms 32164 KB Output is correct
8 Correct 2912 ms 32160 KB Output is correct
9 Correct 3126 ms 32164 KB Output is correct
10 Correct 2939 ms 32164 KB Output is correct
11 Correct 2841 ms 32160 KB Output is correct
12 Correct 2963 ms 32164 KB Output is correct
13 Correct 2966 ms 32160 KB Output is correct
14 Correct 2887 ms 32160 KB Output is correct
15 Correct 2925 ms 32168 KB Output is correct
16 Correct 2909 ms 32164 KB Output is correct
17 Correct 2917 ms 32160 KB Output is correct
18 Correct 3004 ms 32164 KB Output is correct
19 Correct 2867 ms 32160 KB Output is correct
20 Correct 3052 ms 32160 KB Output is correct
21 Correct 2957 ms 32264 KB Output is correct
22 Correct 2875 ms 32160 KB Output is correct
23 Correct 2879 ms 32164 KB Output is correct
24 Correct 2870 ms 32160 KB Output is correct

Subtask #5
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2888 ms 32168 KB Output is correct
2 Correct 2876 ms 32172 KB Output is correct
3 Correct 2872 ms 32200 KB Output is correct
4 Correct 2922 ms 32164 KB Output is correct
5 Correct 2893 ms 32164 KB Output is correct
6 Correct 2989 ms 32164 KB Output is correct
7 Correct 2972 ms 32164 KB Output is correct
8 Correct 2912 ms 32160 KB Output is correct
9 Correct 3126 ms 32164 KB Output is correct
10 Correct 2939 ms 32164 KB Output is correct
11 Correct 2841 ms 32160 KB Output is correct
12 Correct 2963 ms 32164 KB Output is correct
13 Correct 2966 ms 32160 KB Output is correct
14 Correct 2887 ms 32160 KB Output is correct
15 Correct 2925 ms 32168 KB Output is correct
16 Correct 2909 ms 32164 KB Output is correct
17 Correct 2917 ms 32160 KB Output is correct
18 Correct 3004 ms 32164 KB Output is correct
19 Correct 2867 ms 32160 KB Output is correct
20 Correct 3052 ms 32160 KB Output is correct
21 Correct 2957 ms 32264 KB Output is correct
22 Correct 2875 ms 32160 KB Output is correct
23 Correct 2879 ms 32164 KB Output is correct
24 Correct 2870 ms 32160 KB Output is correct
25 Correct 2888 ms 32160 KB Output is correct
26 Correct 2803 ms 32160 KB Output is correct
27 Correct 2929 ms 32164 KB Output is correct
28 Correct 2915 ms 32168 KB Output is correct
29 Correct 2984 ms 32168 KB Output is correct
30 Correct 2926 ms 32164 KB Output is correct