fork download 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ldb long double
  4. #define fi first
  5. #define se second
  6. #define sza(a) (int)a.size()
  7. #define pir pair<int,int>
  8. #define pirll pair<ll,ll>
  9. using namespace std;
  10. const int maxn = 1e5 + 5;
  11. const int alp = 16;
  12.  
  13. ll a[maxn],pw[alp + 2],num[alp + 2],self_digit[alp + 2];
  14.  
  15. void prepare(int alp){
  16. 	pw[0] = 1;
  17. 	for (int i = 1 ; i <= alp ; i++){
  18. 		pw[i] = pw[i - 1] * 10;
  19.  
  20. 		num[i] = pw[i] - pw[i - 1];
  21. 		self_digit[i] = num[i] * i;
  22. 	}
  23. }
  24.  
  25. //get xth digit when laying 123456789101112131415
  26. ll get_digit(ll x){
  27. 	ll res = 0;
  28. 	int digit = 0;
  29.  
  30. 	while (x >= self_digit[digit]){
  31. 		x -= self_digit[digit];
  32. 		digit++;
  33. 	}
  34.  
  35. 	//x == 0, equals last digit, consequencely 9
  36. 	if (!x) return 9;
  37.  
  38. 	ll n = (x - 1)/digit;
  39. 	x -= digit * n;
  40.  
  41. 	n += pw[digit - 1];
  42. 	vector <int> v;
  43. 	while (n > 0){
  44. 		v.push_back(n % 10);
  45. 		n /= 10;
  46. 	}
  47. 	return v[v.size() - x];
  48. }
  49.  
  50. ll sum_digit(ll x){
  51. 	//sum digit 123..x
  52. 	int digit = 0;
  53. 	ll res = 0;
  54.  
  55. 	while (pw[digit] - 1 < x){
  56. 		res += self_digit[digit];
  57. 		digit++;
  58. 	}
  59.  
  60. 	res += (x - pw[digit - 1] + 1) * (ll)digit;
  61. 	return res;
  62. }
  63. //sum digits 1...x
  64. int solve(ll a){
  65. 	ll x = 1;
  66. 	ll len = sum_digit(a);
  67.  
  68. 	while (4*x - 2 <= len) x = 4*x - 2;
  69.  
  70. 	return get_digit(x);
  71. }
  72.  
  73. int main(){
  74. 	ios_base::sync_with_stdio(false);
  75. 	cin.tie(0);cout.tie(0);
  76.  
  77. 	prepare(alp);	
  78.  
  79. 	vector <int> res;
  80.  
  81. 	int n;
  82. 	cin >> n;
  83. 	for (int i = 1 ; i <= n ; i++){
  84. 	   ll a;
  85. 	   cin >> a;
  86. 	   res.push_back(solve(a));	
  87. 	}
  88.  
  89. 	for (int x : res) cout << x;
  90. 	return 0;
  91. }
  92.  
Success #stdin #stdout 0s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
2
https://ideone.com/v0K3Ca
language:
C++14 (gcc 8.3)
created:
1 day 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!