fork download
copy 
  1. // C
  2. #include <bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define int long long
  7. #define bint __int128
  8. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  9.  
  10. int power(int a, int p, int mod) {
  11.     if (p % 2 == 0) return 1;
  12.     return mod - 1;
  13. }
  14.  
  15. void getShitDone() {
  16.     int b, l;
  17.     cin >> b >> l;
  18.  
  19.     int m = 0;
  20.     vector<int> d(l), v(l);
  21.     for (int i = l - 1; i >= 0; --i) {
  22.         cin >> d[i];
  23.         v[i] = power(b, i, b + 1) * d[i] % (b + 1);
  24.         m += v[i], m %= (b + 1);
  25.     }
  26.  
  27.     if (m == 0) {
  28.         cout << 0 << ' ' << 0;
  29.         return;
  30.     }
  31.  
  32.     vector<int> pref = v;
  33.     vector<int> suf = v;
  34.  
  35.     for (int i = 1; i < l; ++i) {
  36.         pref[i] += pref[i - 1];
  37.         pref[i] %= (b + 1);
  38.     }
  39.     for (int i = l - 2; i >= 0; --i) {
  40.         suf[i] += suf[i + 1];
  41.         suf[i] %= (b + 1);
  42.     }
  43.  
  44.     vector<int> to(b + 1);
  45.     for (int i = 0; i <= b; ++i) {
  46.         to[(b * i) % (b + 1)] = i;
  47.     }
  48.  
  49.     for (int i = l - 1, out = 1; i >= 0; --i, ++out) {
  50.         int t = 0;
  51.         if (i + 1 < l) t += suf[i + 1], t %= (b + 1);
  52.         if (i - 1 >= 0) t += pref[i - 1], t %= (b + 1);
  53.         t = ( (b + 1) - t ) % (b + 1);
  54.         int u = power(b, i, b + 1);
  55.         if (u == 1) {
  56.             if (t <= d[i]) {
  57.                 cout << out << ' ' << t;
  58.                 return;
  59.             }
  60.         } else if (to[t] <= d[i]) {
  61.             cout << out << ' ' << to[t];
  62.             return;
  63.         }
  64.     }
  65.     cout << -1 << ' ' << -1;
  66. }
  67.  
  68. signed main() {
  69.     _3bkarm
  70.  
  71.     int ts = 1;
  72. //    cin >> ts;
  73.     while (ts--) getShitDone();
  74.  
  75.     return 0;
  76. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0
https://ideone.com/plsKO3
language:
C++ (gcc 8.3)
created:
15 days 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!