Submission #1344846

#	Time	Username	Problem	Language	Result	Execution time	Memory
1344846		ljtunas	Pancake (NOI12_pancake)	C++20	25 / 25	216 ms	16184 KiB

pancake

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 100005;
const int oo = 1e18 + 5;

int n, a[MAXN], b[MAXN];
map<string, int> dp[MAXN];
string S, T;

int solve(int cnt, string s) {
//    cerr << s << '\n';;
    if (s == T) return cnt;
    if (cnt > n) return oo;
    if (dp[cnt].count(s)) return dp[cnt][s];
    int res = oo;
    for (int i = 1; i <= n; ++i) {
        string x = s;
        for (int j = i; j <= n; ++j) x[j - 1] = s[n - j + i - 1];
        res = min(res, solve(cnt + 1, x));
    }
    return dp[cnt][s] = res;
}

 main() {
    ios::sync_with_stdio(false); cin.tie(0);
    if (fopen("a.inp", "r")) {
        freopen("a.inp", "r", stdin);
        freopen("a.out", "w", stdout);
    }
    int tc;
    cin >> tc;
    while (tc--) {
        cin >> n;
       vector<pair<int, int>> cc;
       for (int i = 1; i <= n; ++i) cin >> a[i], cc.push_back({a[i], i});
       sort(cc.begin(), cc.end());
       for (int i = 0; i < cc.size(); ++i) a[cc[i].second] = i + 1;
       for (int i = 1; i <= n; ++i) b[i] = a[i];
       sort(b + 1, b + n + 1, greater<int>());
       // for (int i = 1; i <= n; ++i) cout << b[i] << ' '; cout << '\n';
        S = "", T = "";
        for (int i = 1; i <= n; ++i) {
            S += char(a[i] + '0');
            T += char(b[i] + '0');
        }
        cout << solve(0, S) << '\n';
    }

    return 0;
}

Compilation message (stderr)

pancake.cpp:26:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   26 |  main() {
      |  ^~~~
pancake.cpp: In function 'int main()':
pancake.cpp:29:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |         freopen("a.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
pancake.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen("a.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 8 / 8
• Subtask 5: 5 / 5