fork download
copy 
  1. #pragma GCC optimize("Ofast")
  2. #pragma GCC target("sse4")
  3. #include <bits/stdc++.h>
  4.  
  5. #define f(i,a,b) for( ll i = a; i < b ; i++ ) 
  6. #define af(i,a,b) for( ll i = a; i >= b ; i--)
  7. #define rep(i,a,b,k) for(ll i = a; i < b ; i+= k )
  8. #define arep(i,a,b,k) for( ll i = a; i >= b ; i-= k)
  9. #define ff first
  10. #define ss second
  11. #define pb push_back
  12. #define mp make_pair
  13. #define sz(a) (int) a.size()
  14. #define all(a) a.begin(), a.end()
  15. #define sor(a) sort( a.begin(), a.end() )
  16. #define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
  17. #define inter ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
  18. #define ln '\n'
  19. #define nwln cout<<ln;
  20. #define v(T) vector<T>
  21. #define mins(i, j) (i = min(i, j))
  22.  
  23. // policy-based
  24. //#include <ext/pb_ds/assoc_container.hpp>
  25. //#include <ext/pb_ds/tree_policy.hpp>
  26. //using namespace __gnu_pbds;   
  27.  
  28.  
  29. using namespace std;
  30.  
  31. typedef bool oo;
  32. typedef long long ll; // int or long long
  33. typedef long double ld;
  34. typedef pair<ll,ll> ii ;
  35. typedef pair<ll,ii> iii;
  36. typedef vector<ll>  vi ;
  37. typedef vector<ii> vii ;
  38.  
  39. /*
  40. typedef tree<
  41. ll,
  42. null_type,
  43. less<ll>,
  44. rb_tree_tag,
  45. tree_order_statistics_node_update>
  46. ordered_set;
  47. */
  48.  
  49. const ll MAX = 100;
  50. const ll inf = 1e18;
  51. const ll mod = 1e9 + 7;
  52. const ld EPS = 1e-9;
  53.  
  54. vi val[MAX+1][MAX+1];
  55. set<vi> s;
  56.  
  57. bool vis[MAX][MAX],c[MAX][MAX];
  58.  
  59. int cc = 0;
  60.  
  61. bool valid(int x,int y){
  62. 	if(x<0 || y<0 || x>=MAX || y>=MAX || !c[x][y] || vis[x][y])
  63. 		return false;
  64. 	return true;
  65. }
  66.  
  67. void dfs(int x,int y){
  68. 	cc++;
  69. //	cout << x << " -"  << y  << endl;
  70. 	vis[x][y] = true;
  71. 	if(valid(x-1,y))
  72. 		dfs(x-1,y);
  73. 	if(valid(x+1,y))
  74. 		dfs(x+1,y);
  75. 	if(valid(x,y-1))
  76. 		dfs(x,y-1);
  77. 	if(valid(x,y+1))
  78. 		dfs(x,y+1);
  79. }
  80.  
  81. void comprobe(vii v){
  82. 	for(int i = 0; i < MAX; i++)
  83. 		for(int j = 0; j < MAX; j++) c[i][j] = vis[i][j] = false;		
  84. 	for(auto it:v){
  85. 		c[it.first][it.second] = true;
  86. 	}
  87. //	cout <<  endl;
  88. //	f(i,0,MAX){
  89. //		f(j,0,MAX) cout << (int) (c[i][j]);
  90. //		cout << endl;
  91. //	}
  92. 	dfs(v[0].first,v[0].second);
  93. 	cout << cc << " " << v.size() << endl;
  94. 	cc = 0;
  95. }
  96.  
  97. int main(){
  98. 	int n;
  99. 	cin >> n;
  100. 	int k = 0;
  101. 	while( (1<<k) < n ) k++;
  102. 	cout << k << endl;
  103. 	for(int b = 0; b < 6; b++){	
  104. 		if(!k) break;
  105. 		k--;
  106. 		vii p;
  107. 		for(int i = 0; i < MAX; i++){
  108. 			p.push_back({i,0});
  109. 		}
  110. 		for(int i = 0; i < MAX; i++){
  111. 			if(i&(1<<b)){
  112. 				for(int j = 1; j < MAX; j++){
  113. 					p.push_back({i,j});
  114. 				}
  115. 			}
  116. 		}
  117.  
  118. 		comprobe(p);
  119. 	//	cout << p.size();
  120. 	//	for(auto it:p) cout << " " << it.first << " " << it.second;
  121. 	//	cout << endl;
  122.  
  123. 		for(auto it:p){
  124. 			val[it.first][it.second].push_back(b);
  125. 		}
  126.  
  127. 	}
  128. 	for(int b = 0; b < 6; b++){	
  129. 		if(!k) break;
  130. 		k--;
  131. 		vii p;
  132. 		for(int i = 0; i < MAX; i++){
  133. 			p.push_back({0,i});
  134. 		}
  135. 		for(int i = 0; i < MAX; i++){
  136. 			if(i&(1<<b)){
  137. 				for(int j = 1; j < MAX; j++){
  138. 					p.push_back({j,i});
  139. 				}
  140. 			}
  141. 		}
  142. 		comprobe(p);
  143. 	//	cout << p.size();
  144. 	//	for(auto it:p) cout << " " << it.first << " " << it.second;
  145. 	//	cout << endl;
  146.  
  147. 		for(auto it:p){
  148. 			val[it.first][it.second].push_back(6+b);
  149. 		}
  150. 	}
  151. 	for(int i = 0; i < MAX; i++) 
  152. 		for(int j = 0; j < MAX; j++) s.insert(val[i][j]);
  153.  
  154. 	cout << s.size() << endl;
  155. //	for(auto it:s) {
  156. //		for(auto x:it) cout << x << " ";
  157. //			cout << endl;
  158. //	}
  159. 	return 0;
  160. }
Success #stdin #stdout 0.01s 5584KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
13
5050 5050
5050 5050
4852 4852
4852 4852
4852 4852
3664 3664
5050 5050
5050 5050
4852 4852
4852 4852
4852 4852
3664 3664
4096
https://ideone.com/JpyUC7
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!