oj.uz

답안 #923797

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
923797 2024-02-07T19:17:21 Z Ianis Cheerleaders (info1cup20_cheerleaders) C++17
56 / 100
 908 ms 2764 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>;

const int NMAX = 17;

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() {
   int best = 0;
   ll best_inv = 1 << (2 * 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
0.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Correct!
2 Correct 1 ms 348 KB Correct!
3 Correct 0 ms 348 KB Correct!
4 Correct 1 ms 348 KB Correct!

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 348 KB Correct!
2 Correct 6 ms 344 KB Correct!
3 Correct 6 ms 348 KB Correct!
4 Correct 6 ms 504 KB Correct!

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 106 ms 1012 KB Correct!
2 Correct 106 ms 1104 KB Correct!
3 Correct 265 ms 1372 KB Correct!

Subtask #5
0.0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 908 ms 2764 KB Wrong number of inversions
2 Halted 0 ms 0 KB -