oj.uz

Submission #515710

# Submission time Handle Problem Language Result Execution time Memory
515710 2022-01-19T14:17:45 Z cadmiumsky Cheerleaders (info1cup20_cheerleaders) C++14
100 / 100
 504 ms 11876 KB 
#include <bits/stdc++.h>

using namespace std;
#define ll long long

int n;
int bit;
int v[(1<<17) + 5];
ll freq[(1<<17) + 5];
int inf;
static ll solve(vector<int> p, int crit = 0, int b = bit - 1) {
  //cout << b << '\n';
  if(b <= -1)
    return 0;
  ll total[2] = {0, 0};
  int temp = crit;
  while(temp) {
    freq[temp] = 0;
    temp = (temp - 1) & crit;
  }
  freq[0] = 0;
  for(auto x : p) {
    if((x & (1 << b)))
      freq[x & crit]++;
    else
      total[0] += freq[x & crit];
    //cout << (x&crit) <<  ' '<< (x&(1<<b)) <<" / ";
  }
  //cout << '\n';
  temp = crit;
  while(temp) {
    freq[temp] = 0;
    temp = (temp - 1) & crit;
  }
  freq[0] = 0;
  for(auto x : p) {
    if(!(x & (1 << b)))
      freq[x & crit]++;
    else
      total[1] += freq[x & crit];
  }
  if(total[0] >= total[1])
    inf |= (1 << b);
  //cout << total[0] << ' ' << total[1] << '\n';
  return min(total[0], total[1]) + solve(p, crit | (1 << b), b - 1);
}

int main() {
  cin >> bit;
  n = (1 << bit);
  for(int i = 0, x; i < n; i++) {
    cin >> x;
    v[x] = i;
  }
  if(bit == 0) {
    cout << "0\n2\n";
    return 0;
  }
  ll minn = (1LL << 35);
  int sol = 0;
  string pref, current = "";
  for(int fix = bit - 1; fix >= 0; fix--) {
    vector<int> temp(n, 0);
    for(int i = 0; i < n; i++)
      temp[i] = v[i];
    inf = 0;
    ll total = solve(temp);
    if(minn > total) {
      minn = total;
      pref = current;
      sol = inf;
    }
    for(int i = 0; i < n; i++)
      v[i] = ((v[i] >> 1) | ((v[i] & 1) << bit - 1));
    current += "2";
  }
  cout << minn << '\n';
  cout << pref;
  if(sol & (1 << bit - 1))
    cout << 1;
  cout << 2;
  for(int i = 0; i < bit - 1; i++) {
    if(sol & (1 << i))
      cout << 1;
    cout << 2;
  }
  cout << '\n';
}

Compilation message

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:74:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   74 |       v[i] = ((v[i] >> 1) | ((v[i] & 1) << bit - 1));
      |                                            ~~~~^~~
cheerleaders.cpp:79:22: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   79 |   if(sol & (1 << bit - 1))
      |                  ~~~~^~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Correct!
2 Correct 0 ms 204 KB Correct!
3 Correct 0 ms 300 KB Correct!
4 Correct 0 ms 204 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 272 KB Correct!
2 Correct 1 ms 204 KB Correct!
3 Correct 1 ms 204 KB Correct!
4 Correct 1 ms 204 KB Correct!

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 436 KB Correct!
2 Correct 3 ms 332 KB Correct!
3 Correct 3 ms 332 KB Correct!
4 Correct 3 ms 332 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 3064 KB Correct!
2 Correct 52 ms 3068 KB Correct!
3 Correct 140 ms 6020 KB Correct!

Subtask #5
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 337 ms 11716 KB Correct!
2 Correct 367 ms 11876 KB Correct!
3 Correct 497 ms 11576 KB Correct!
4 Correct 503 ms 11580 KB Correct!
5 Correct 504 ms 11696 KB Correct!