oj.uz

Submission #923805

# Submission time Handle Problem Language Result Execution time Memory
923805 2024-02-07T19:38:34 Z Ianis Cheerleaders (info1cup20_cheerleaders) C++17
72 / 100
 2000 ms 3768 KB 
#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>;

#define int int64_t

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, int mx = INF) {
   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);
      if (cnt >= mx)
         return mx + 1;
      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), inv);
         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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Correct!
2 Correct 1 ms 2392 KB Correct!
3 Correct 0 ms 2396 KB Correct!
4 Correct 1 ms 2396 KB Correct!

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2396 KB Correct!
2 Correct 1 ms 2396 KB Correct!
3 Correct 1 ms 2392 KB Correct!
4 Correct 1 ms 2396 KB Correct!

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2396 KB Correct!
2 Correct 6 ms 2396 KB Correct!
3 Correct 6 ms 2396 KB Correct!
4 Correct 6 ms 2396 KB Correct!

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 2904 KB Correct!
2 Correct 116 ms 2748 KB Correct!
3 Correct 336 ms 2904 KB Correct!

Subtask #5
0.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1322 ms 3768 KB Correct!
2 Correct 1345 ms 3508 KB Correct!
3 Execution timed out 2045 ms 3672 KB Time limit exceeded
4 Halted 0 ms 0 KB -