提出 #72068732

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define pb emplace_back
using namespace std;
const int N = 1e6 + 7, mod = 998244353;

int n;
vi compute_next(int a) {
    vi outs;
    L(sub, 0, (1 << n) - 1) {
        vi pos;
        vi npos;
        L(d, 0, n - 1)
            if(sub >> d & 1)
                pos.pb(d);
            else 
                npos.pb(d);
        int res = 0;
        L(o, 0, 1) {
            L(i, 0, sz(pos) - 1)
                if(a >> pos[i] & 1)
                    res |= 1 << pos[sz(pos) - i - 1];
            swap(pos, npos);
        }
        outs.pb(res);
    }
    return outs;
}
vi operate(vi a, string s) {
    vi pos;
    vi npos;
    L(d, 0, n - 1)
        if(s[d] == 'A')
            pos.pb(d);
        else 
            npos.pb(d);
    vi b(n);
    int res = 0;
    L(o, 0, 1) {
        L(i, 0, sz(pos) - 1)
            if(a[pos[i]])
                b[pos[sz(pos) - i - 1]] = 1;
        swap(pos, npos);
    }
    return b;
}

bool inc(vi a) {
    L(i, 1, n - 1) if(a[i - 1] > a[i])return false;
    return true;
}

vector<string>solve(vi a){
    assert(n == sz(a));
    int cnt1 = 0;
    L(i, 0, sz(a) - 1) cnt1 += a[i];
    if(cnt1 > n / 2) {
        vi b = a;
        reverse(b.begin(), b.end());
        for(auto&u : b)
            u = 1 - u;
        auto ns = solve(b);
        for(auto&p : ns)
            reverse(p.begin(), p.end());
        return ns;
    }
    vector<string>ans;
    if(inc(a)) {
        return ans;
    }
    int ok_1 = true;
    int pref_1 = 0;
    int suf_0 = 0;
    while(a[pref_1] == 1) ++pref_1;
    while(a[n - suf_0 - 1] == 0) ++suf_0;
    int num = 0;
    L(i, pref_1, n - cnt1 - 1)
        num += a[i];
    //cout << num << ',' << suf_0 << endl;
    if(num <= suf_0) {
        string ret;
        L(t, 1, n) ret += "A";
        int qwq = cnt1 - pref_1;
        L(i, pref_1, n - 1) if(a[i] == 1) ret[i] = 'B'; 
        L(i, n - num, n - 1) ret[i] = 'B';  
        //cout << "RET = " << ret << endl;
        ans.pb(ret);
        vi na = operate(a, ret);
        if(!inc(na)) assert(false);
        return ans;
    }
    string ret;
    int cnt[2] = {0, 0};
    int half = n / 2;
    L(i, 0, half - 1)
        if(a[i])
            ++cnt[1], ret += "B";
        else 
            ++cnt[0], ret += "A";
    if(n & 1)
        ret += "B";
    L(i, 1, cnt[1])
        ret += "B";
    L(i, 1, cnt[0])
        ret += "A";
    vi b = operate(a, ret);
    //cout << "ret = " << ret << endl;
    //for(auto&u : b)
    //    cout << u << ' ';
    //cout << endl;
    ans=solve(b);
    
    ans.insert(ans.begin(), ret);
    return ans;
}
queue<int>q;
int dis[N];
void sanity() {
    n = 10;
    L(i, 0, (1 << n) - 1) dis[i] = n + 1;
    L(i, 0, n) {
        dis[(1 << n) - (1 << i)] = 0;
        q.push((1 << n) - (1 << i));
    }
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        auto nw = compute_next(u);
        for(auto&p : nw) {
            if(dis[p] > dis[u] + 1) {
                dis[p] = dis[u] + 1;
                q.push(p);
            }
        }
    }
    cout << *max_element(dis, dis + (1 << n)) << '\n';
}
int main () {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    //mt19937 rng;
    //n = 9;
    //L(t, 1, 2000) {
    //    vi a(n);
    //    L(i, 0, n - 1) a[i] = rng() & 1;
    //    cout << "a = " << endl;
    //    int cnt1 = 0;
    //    L(i, 0, n - 1)
    //        cnt1 += a[i];
    //    auto ns = solve(a);
    //    for(auto&p : ns)
    //        a = operate(a, p);
    //    assert(inc(a));
    //    cout << "AFTER " << t << endl;
    //}
    int t; 
    cin >> t; 
    while(t--) {
        cin >> n;
        vi a(n);
        L(i, 0, n - 1) cin >> a[i];
        auto ans = solve(a);
        cout << sz(ans) << '\n';
        for(auto&u : ans){
            cout << u << '\n';
        }
    }
    return 0;
} 

提出情報

コンパイルエラー

./Main.cpp: In function 'std::vector<int> operate(std::vector<int>, std::string)':
./Main.cpp:44:9: warning: unused variable 'res' [-Wunused-variable]
   44 |     int res = 0;
      |         ^~~
./Main.cpp: In function 'std::vector<std::__cxx11::basic_string<char> > solve(std::vector<int>)':
./Main.cpp:89:13: warning: unused variable 'qwq' [-Wunused-variable]
   89 |         int qwq = cnt1 - pref_1;
      |             ^~~
./Main.cpp:77:9: warning: unused variable 'ok_1' [-Wunused-variable]
   77 |     int ok_1 = true;
      |         ^~~~

ジャッジ結果