fork download 
  1. #include<bits/stdc++.h>
  2. #define pb(x) push_back(x)
  3. #define all(x) x.begin(), x.end()
  4. #define cout2(x, y) cout << x << " " << y <<  endl
  5. #define N 100004
  6. #define INF (1LL<<40)
  7.  
  8. using namespace std;
  9.  
  10. long long a[N];
  11. bool vis[N];
  12.  
  13. long long trans(string &s){
  14.  
  15. 	long long ans = 0;
  16. 	if(s[0] == '-'){
  17.  
  18. 		for(int i = 1; i < s.size(); i++)ans = ans * 10 + s[i] - '0';
  19. 		return -1 * ans;	
  20. 	}
  21.  
  22. 	for(int i = 0; i < s.size(); i++)ans = ans * 10 + s[i] - '0';
  23. 	return ans;
  24.  
  25. }
  26.  
  27. long long F(long long val, long long n){
  28.  
  29.  
  30. 	if(val + n - 1 <= 0)return abs(val * n) + n * (n - 1)/2;
  31. 	if(val >= 0)return abs(val * n) + n * (n - 1)/2;
  32.  
  33. 	n = abs(abs(val) - abs(val + n - 1));
  34. 	return val * n + n * (n - 1)/2;
  35.  
  36.  
  37. }
  38.  
  39. bool solve(vector<long long>&seq){
  40.  
  41. 	int n = seq.size() - 2;
  42.  
  43. 	long long menor = seq[0], mayor = seq.back();
  44. 	if(mayor - menor - 1 < n)return false;
  45.  
  46. 	long long lo = menor + 2 * INF + 1, hi = mayor + 2 * INF - n, me1, me2;
  47.  
  48. 	while(hi - lo > 3){
  49.  
  50. 		me1 = (2 * lo + hi)/3;
  51. 		me2 = (lo + 2 * hi)/3;
  52.  
  53. 		if(F(me1 - 2 * INF, n) > F(me2 - 2 * INF, n))lo = me1;
  54. 		else hi = me2;
  55.  
  56. 	}
  57.  
  58.  
  59. 	lo -= 2 * INF;
  60. 	hi -= 2 * INF;
  61.  
  62. 	long long pos = lo;
  63. 	for(long long i = lo; i <= hi; i++)if(F(pos, n) > F(i, n))pos = i;
  64.  
  65. 	for(int i = 1; i < seq.size() - 1; i++)a[seq[i]] = pos + i - 1;
  66. 	return true;
  67. }
  68.  
  69. int main(){
  70.  
  71. 	int n, k;
  72. 	while(cin>>n>>k){
  73.  
  74. 		string s, aux;
  75. 		getline(cin, s);
  76.  
  77. 		getline(cin, s);
  78. 		istringstream in(s);
  79.  
  80. 		for(int i = 0; i < n; i++){
  81.  
  82. 			in>>aux;
  83. 			if(aux == "?")a[i] = INF;
  84. 			else a[i] = trans(aux);
  85. 		}
  86.  
  87. 		memset(vis, false, sizeof vis);
  88.  
  89. 		vector<vector<long long> >S;
  90. 		vector<long long>seq;
  91.  
  92. 		for(int i = 0; i < n; i++){
  93.  
  94. 			if(vis[i])continue;
  95. 			if(a[i] != INF)continue;
  96.  
  97. 			seq.clear();
  98. 			if(i - k >= 0)seq.pb(a[i - k]);
  99. 			else seq.pb(-INF);
  100.  
  101. 			while(i < n && a[i] == INF)seq.pb(i), vis[i] = true, i += k;
  102.  
  103. 			if(i < n)seq.pb(a[i]);
  104. 			else seq.pb(INF);
  105.  
  106. 			S.pb(seq);
  107. 		}
  108.  
  109. 		bool ok = true;
  110. 		for(int i = 0; i < S.size() && ok; i++)if(!solve(S[i]))ok = false;
  111.  
  112. 		for(int i = 0; i < n; i++){
  113.  
  114. 			if(i - k >= 0 && a[i - k] >= a[i])ok = false;	
  115. 			if(i + k < n && a[i + k] <= a[i])ok = false;	
  116. 		}
  117.  
  118. 		if(ok){
  119.  
  120. 			printf("%I64d", a[0]);
  121. 			for(int i = 1; i < n; i++)printf(" %I64d", a[i]);
  122. 			puts("");
  123. 		}
  124. 		else puts("Incorrect sequence");
  125. 	}
  126.  
  127.  
  128. }
  129.  
  130.  
  131.  
Success #stdin #stdout 0s 4028KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/4rPyfc
language:
C++ (gcc 8.3)
created:
9 years 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!