fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<long long> solve(vector<int>& array) {
  5.  
  6.     int m = array.size() - 1;
  7.  
  8.     vector<long long> res(m + 1);
  9.     vector<int> a(m + 1), k(m + 1);
  10.  
  11.     long long a_sum = 0, k_sum = 0;
  12.     long long ac = 0, kc = 0;
  13.  
  14.     for (int i = 1; i <= m; i++) {
  15.         if (array[i] == 1) {
  16.             a[i] = 1;
  17.             ac++;
  18.             a_sum += i;
  19.         }
  20.         else if (array[i] == 2) {
  21.             k[i] = 1;
  22.             kc++;
  23.             k_sum += i;
  24.         }
  25.         else if (array[i] == 3) {
  26.             a[i] = 1;
  27.             k[i] = 1;
  28.             ac++;
  29.             kc++;
  30.             a_sum += i;
  31.             k_sum += i;
  32.         }
  33.     }
  34.  
  35.     vector<long long> aarsi(m + 1), krypto(m + 1);
  36.  
  37.     long long left_arsi = 0, left_krypto = 0;
  38.     long long lt_arsi_sum = 0, lt_krypto_sum = 0;
  39.  
  40.     // Aarsi
  41.     for (int line = 1; line <= m; line++) {
  42.         long long d = 0, w = 0;
  43.         if (a[line]) {
  44.             left_arsi++;
  45.             lt_arsi_sum += line;
  46.             d = 1;
  47.             w = line;
  48.         }
  49.  
  50.         long long left_score = left_arsi * line - lt_arsi_sum;
  51.         long long right_score =
  52.             (a_sum - lt_arsi_sum + w) - (ac - left_arsi + d) * line;
  53.  
  54.         aarsi[line] = left_score + right_score;
  55.     }
  56.  
  57.     // Krypto
  58.     for (int line = 1; line <= m; line++) {
  59.         long long d = 0, w = 0;
  60.         if (k[line]) {
  61.             left_krypto++;
  62.             lt_krypto_sum += line;
  63.             d = 1;
  64.             w = line;
  65.         }
  66.  
  67.         long long left_score = left_krypto * line - lt_krypto_sum;
  68.         long long right_score =
  69.             (k_sum - lt_krypto_sum + w) - (kc - left_krypto + d) * line;
  70.  
  71.         krypto[line] = left_score + right_score;
  72.     }
  73.  
  74.     for (int i = 1; i <= m; i++) {
  75.         res[i] = llabs(aarsi[i] - krypto[i]);
  76.     }
  77.  
  78.     return res;
  79. }
  80.  
  81. int main() {
  82.     ios::sync_with_stdio(false);
  83.     cin.tie(nullptr);
  84.  
  85.     int t;
  86.     cin >> t;
  87.  
  88.     while (t--) {
  89.         int dummy, m;
  90.         cin >> dummy >> m;
  91.  
  92.         vector<int> array(m + 1);
  93.         for (int i = 1; i <= m; i++) {
  94.             cin >> array[i];
  95.         }
  96.  
  97.         vector<long long> res = solve(array);
  98.         for (int i = 1; i <= m; i++) {
  99.             cout << res[i] << " ";
  100.         }
  101.         cout << "\n";
  102.     }
  103. }
  104.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
2
1 5
2 1 3 0 1
1 8
1 1 3 0 2 0 3 3
stdout
copy 
5 2 1 0 1 
3 2 1 4 7 8 9 10
https://ideone.com/rrucMK
language:
C++ (gcc 8.3)
created:
5 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!