Submission #515703

#	Time	Username	Problem	Language	Result	Execution time	Memory
515703		cadmiumsky	Cheerleaders (info1cup20_cheerleaders)	C++14	46 / 100	477 ms	12396 KiB

cheerleaders

#include <bits/stdc++.h>

using namespace std;
#define ll long long

int n;
int bit;
int v[(1<<17) + 5];
int freq[(1<<17) + 5];
string 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";
  inf += "2";
  //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;
  }
  ll minn = (1LL << 35);
  string sol, 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 = current;
    ll total = solve(temp);
    if(minn > total) {
      minn = total;
      sol = inf;
    }
    for(int i = 0; i < n; i++)
      v[i] = ((v[i] >> 1) | ((v[i] & 1) << bit - 1));
    current += "2";
  }
  cout << minn << '\n' << sol << '\n';
}

Compilation message (stderr)

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

• Subtask 1: 0 / 16
• Subtask 2: 5 / 10
• Subtask 3: 20 / 25
• Subtask 4: 0 / 21
• Subtask 5: 21 / 28