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
stdin
Standard input is empty
stdout
Standard output is empty