Submission #923811

#	Time	Username	Problem	Language	Result	Execution time	Memory
923811		Ianis	Cheerleaders (info1cup20_cheerleaders)	C++17	100 / 100	1192 ms	2896 KiB

cheerleaders

#ifdef LOCAL
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <random>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#else
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define cerr if (false) cerr 
#define endl '\n'
#endif

#define fi first
#define se second

#define sz(a) ((int)(a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))

#define bit(mask, i) (((mask) >> (i)) & 1)
#define popcount(x) __builtin_popcount(x)

#define YES cout << "YES" << endl
#define NO cout << "NO" << endl

using namespace std;

template <typename T>
bool ckmax(T &a, T b) { return a < b ? a = b, true : false; }
template <typename T>
bool ckmin(T &a, T b) { return a > b ? a = b, true : false; }

using ll = long long;
using pii = pair<int, int>;

const int NMAX = 17;
const ll INF = 1e18+5;

int n;
int a[(1 << NMAX) + 5];
int pos[(1 << NMAX) + 5];
int aib[(1 << NMAX) + 5];
int xor_val[NMAX];
string ans;

void aib_update(int pos, int val) {
   pos++;
   for (int i = pos; i <= 1 << n; i += lsb(i))
      aib[i] += val;
}

int aib_query(int pos) {
   pos++;
   int sum = 0;
   for (int i = pos; i >= 1; i -= lsb(i))
      sum += aib[i];
   return sum;
}

ll cnt_inv(int mask) {
   fill(aib, aib + (1 << n) + 1, 0);
   ll cnt = 0;
   for (int i = (1 << n) - 1; i >= 0; i--) {
      cnt += aib_query(pos[i] ^ mask);
      aib_update(pos[i] ^ mask, 1);
   }
   return cnt;
}

void read() {
   cin >> n;
   for (int i = 0; i < 1 << n; i++) {
      cin >> a[i];
      pos[a[i]] = i;
   }
}

int cycle(int x, int cnt) {
   cnt %= n;
   return (x >> cnt) | ((x & ((1 << cnt) - 1)) << (n - cnt));
}

void cycle_all(int cnt) {
   for (int i = 0; i < 1 << n; i++)
      pos[i] = cycle(pos[i], cnt);
}

void ans_xor(int val) {
   if (bit(val, n - 1))
      ans.push_back('1');
   ans.push_back('2');

   for (int i = 0; i < n - 1; i++) {
      if (bit(val, i))
         ans.push_back('1');
      ans.push_back('2');
   }
}

void solve() {
   if (n == 0) {
      cout << 0 << endl;
      return;
   }
   int best = 0;
   ll best_inv = 1ll << (2ll * n);

   for (int shift = 0; shift < n; shift++) {
      ll inv = cnt_inv(0);

      for (int i = n - 1; i >= 0; i--) {
         ll inv1 = cnt_inv(xor_val[shift] ^ (1 << i));
         if (inv1 < inv) {
            inv = inv1;
            xor_val[shift] ^= 1 << i;
         }
      }

      if (ckmin(best_inv, inv)) {
         best = shift;
      }
      
      cycle_all(1);
   }

   cycle_all(best);
   ans = string(best, '2');
   ans_xor(xor_val[best]);

   cout << best_inv << endl << ans << endl;
}

signed main() {
#ifdef LOCAL
   freopen("input.txt", "r", stdin);
#endif
   ios_base::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   
   read();
   solve();

   return 0;
}

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