Advertisement
YEZAELP

B. Divine Array

Oct 31st, 2021
914
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 2e3 + 10;
  5. int ar[N][N];
  6. int cnt[N];
  7.  
  8. void Solve(){
  9.     int n;
  10.     scanf("%d", &n);
  11.  
  12.     int ar[n + 1][n + 1];
  13.     int cnt[n + 1];
  14.     for(int i=1;i<=n;i++) cnt[i] = 0;
  15.  
  16.     for(int j=1;j<=n;j++){
  17.         scanf("%d", &ar[0][j]);
  18.         cnt[ ar[0][j] ] ++;
  19.     }
  20.  
  21.     bool found = true;
  22.     int last = 0;
  23.     for(int i=1;i<=n and found;i++){
  24.         for(int j=1;j<=n;j++){
  25.             ar[i][j] = cnt[ ar[i-1][j] ];
  26.         }
  27.         for(int j=1;j<=n;j++){
  28.             cnt[j] = 0;
  29.         }
  30.         for(int j=1;j<=n;j++){
  31.             cnt[ ar[i][j] ] ++;
  32.         }
  33.         found = false;
  34.         for(int j=1;j<=n;j++){
  35.             if(cnt[j] != j and cnt[j] != 0) found = true;
  36.         }
  37.         last = i;
  38.     }
  39.  
  40.     int q;
  41.     scanf("%d", &q);
  42.  
  43.     while(q--){
  44.         int j, k;
  45.         scanf("%d%d", &j, &k);
  46.         if(k <= last) printf("%d\n", ar[k][j]);
  47.         else printf("%d\n", ar[last][j]);
  48.     }
  49.  
  50. }
  51.  
  52. int main(){
  53.  
  54.     int t;
  55.     scanf("%d", &t);
  56.  
  57.     while(t--){
  58.         Solve();
  59.     }
  60.  
  61.     return 0;
  62. }
Advertisement
RAW Paste Data Copied
Advertisement