oj.uz

Submission #242624

# Submission time Handle Problem Language Result Execution time Memory
242624 2020-06-28T11:15:20 Z SamAnd Pancake (NOI12_pancake) C++17
25 / 25
 207 ms 6904 KB 
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 10;

map<vector<int>, int> d;

void bfs(vector<int> s)
{
    d[s] = 0;
    queue<vector<int> > q;
    q.push(s);
    while (!q.empty())
    {
        vector<int> v = q.front();
        q.pop();
        for (int u = sz(v) - 1; u >= 0; --u)
        {
            vector<int> h = v;
            for (int i = u, j = sz(v) - 1; i < sz(v); ++i, --j)
            {
                h[i] = v[j];
            }
            if (d.find(h) == d.end())
            {
                d[h] = d[v] + 1;
                q.push(h);
            }
        }
    }
}

void pre()
{
    for (int i = 0; i < 8; ++i)
    {
        vector<int> v;
        for (int j = i; j >= 0; --j)
            v.push_back(j);
        bfs(v);
    }
}

int n;
int a[N];

void solv()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &a[i]);
    vector<pair<int, int> > v;
    for (int i = 0; i < n; ++i)
    {
        v.push_back(m_p(a[i], i));
    }
    sort(all(v));
    vector<int> u(n);
    for (int i = 0; i < n; ++i)
    {
        u[v[i].se] = i;
    }
    assert(d.find(u) != d.end());
    printf("%d\n", d[u]);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    pre();
    int tt;
    scanf("%d", &tt);
    while (tt--)
        solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}

Compilation message

pancake.cpp: In function 'void solv()':
pancake.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
pancake.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
pancake.cpp: In function 'int main()':
pancake.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &tt);
     ~~~~~^~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 6776 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 6776 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 6776 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 6904 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 6904 KB Output is correct