fork download
copy 
  1. /* Author : Triet Do Thanh - FPT University */
  2.  
  3. #include <bits/stdc++.h>
  4.  
  5. #define endl           '\n'
  6. #define int            long long
  7.  
  8. using namespace        std;
  9.  
  10. typedef pair<int, int> ii;
  11.  
  12. const int       N      = 3e6 + 7;
  13. const long long oo     = 1e18 + 7;
  14. const long long MOD    = 1e9 + 7;
  15.  
  16. int n;
  17. int a[N];
  18. vector<int>pos[N], p[N];
  19.  
  20. int pointer[N];
  21.  
  22. int d[N * 2];
  23.  
  24. void sieve() {
  25.    d[0] = d[1] = 1;
  26.    for (int i = 2; i * i <= N; ++i) {
  27.       if (d[i] == 0) {
  28.          for (int j = i; j * i <= N; ++j) d[i * j] = 1;
  29.       }
  30.    }
  31. }
  32.  
  33. void solve() {
  34.    cin >> n;
  35.    for (int i = 1; i <= n; ++i) cin >> a[i];
  36.    sieve();
  37.    for (int i = 1; i <= n; ++i) {
  38.       for (int div = 2; div <= a[i]; ++div) {
  39.          if (d[a[i]] == 0) {
  40.             pos[a[i]].push_back(i);
  41.             p[i].push_back(a[i]);
  42.             a[i] = 1;
  43.             break;
  44.          }
  45.          if (a[i] % div == 0)  {
  46.             pos[div].push_back(i);
  47.             p[i].push_back(div);
  48.             while (a[i] % div == 0) {
  49.                a[i] /= div;
  50.             }
  51.          }
  52.       }
  53.    }
  54.    //for (int &it : pos[2]) cout << it << ' ';
  55.  
  56.    for (int i = 1; i <= n; ++i) {
  57.       int ans = oo;
  58.       int res = -1;
  59.       for (int div : p[i]) {
  60.          if ((int)pos[div].size() < 2) continue;
  61.          int vt = lower_bound(pos[div].begin(), pos[div].end(), i) - pos[div].begin();
  62.          if (vt == 0) {
  63.             if (pos[div][vt + 1] - pos[div][vt] < ans) { 
  64.                ans = pos[div][vt + 1] - pos[div][vt];
  65.                res = pos[div][vt + 1];
  66.             }
  67.          }
  68.          else if (vt == (int)pos[div].size() - 1) {
  69.             if (pos[div][vt] - pos[div][vt - 1] <= ans) { 
  70.                ans = pos[div][vt] - pos[div][vt - 1];
  71.                res = pos[div][vt - 1];
  72.             }
  73.          }
  74.          else {
  75.             if (pos[div][vt + 1] - pos[div][vt] < ans) { 
  76.                ans = pos[div][vt + 1] - pos[div][vt];
  77.                res = pos[div][vt + 1];
  78.             }
  79.             if (pos[div][vt] - pos[div][vt - 1] <= ans) { 
  80.                ans = pos[div][vt] - pos[div][vt - 1];
  81.                res = pos[div][vt - 1];
  82.             }
  83.          }
  84.       }
  85.       cout << res <<' ';
  86.    }
  87.  
  88. }
  89.  
  90. #define TASK "test"
  91.  
  92. signed main()
  93. {
  94.    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  95.    if (fopen("input.txt", "r")) {
  96.       freopen("input.txt", "r", stdin);
  97.       freopen("output.txt", "w", stdout);
  98.    }
  99.    solve();
  100.    return 0;
  101. }
Success #stdin #stdout 0.08s 169708KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FCNFlp
language:
C++14 (gcc 8.3)
created:
2 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!