Submission #845476

#	Time	Username	Problem	Language	Result	Execution time	Memory
845476		samekkk	Cheerleaders (info1cup20_cheerleaders)	C++14	26 / 100	2101 ms	26252 KiB

cheerleaders

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a,b) for (int a = 0; a < (b); ++a)
#define pb push_back
#define all(t) t.begin(), t.end()

struct Element
{
    vector<int> V;
    string ciag;
};

const int max_N = 3e6+5;
int n = 0, wyn = 1e9+20;
int A[max_N];
string wyn_ciag;
set<vector<int>> S;
queue<Element> Q;
vector<int> V;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    n = (1 << n);
    if(n == 1)
    {
        cout << "0" << '\n' << '\n';
        return 0;
    }
    rep(i,n) cin >> A[i];
    V.assign(n,-1);
    rep(i,n) V[i] = A[i];
    S.insert(V), Q.push({V,""});
    while(!Q.empty())
    {
        Element spr = Q.front();
        Q.pop();
        int ile = 0;
        rep(i,n) for (int j = i+1; j < n; ++j) if(spr.V[i] > spr.V[j]) ++ile;
        //for (auto x : spr.V) cout << x << " ";
        //cout << endl;
        //cout << spr.ciag << endl;
        //cout << ile << endl << endl << endl;
        if (ile < wyn)
        {
            wyn = ile, wyn_ciag = spr.ciag;
        }
        vector<int> vect;
        for (int i = n/2; i < n; ++i) vect.pb(spr.V[i]);
        rep(i,n/2) vect.pb(spr.V[i]);
        if (auto it = S.find(vect) == S.end())
        {
            S.insert(vect);
            Q.push({vect,spr.ciag+"1"});
        }
        vect = vector<int>();
        for (int i = 0; i < n; i+=2) vect.pb(spr.V[i]);
        for (int i = 1; i < n; i+=2) vect.pb(spr.V[i]);
        if (auto it = S.find(vect) == S.end())
        {
            S.insert(vect);
            Q.push({vect,spr.ciag+"2"});
        }
    }
    cout << wyn << '\n' << wyn_ciag << '\n';
    return 0;
}

Compilation message (stderr)

cheerleaders.cpp: In function 'int main()':
cheerleaders.cpp:56:18: warning: unused variable 'it' [-Wunused-variable]
   56 |         if (auto it = S.find(vect) == S.end())
      |                  ^~
cheerleaders.cpp:64:18: warning: unused variable 'it' [-Wunused-variable]
   64 |         if (auto it = S.find(vect) == S.end())
      |                  ^~

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