Submission #515710

#	Time	Username	Problem	Language	Result	Execution time	Memory
515710		cadmiumsky	Cheerleaders (info1cup20_cheerleaders)	C++14	100 / 100	504 ms	11876 KiB

cheerleaders

#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 (stderr)

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 / 16
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 21 / 21
• Subtask 5: 28 / 28