Submission #385012

#	Time	Username	Problem	Language	Result	Execution time	Memory
385012		arwaeystoamneg	Mechanical Doll (IOI18_doll)	C++17	2 / 100	95 ms	12336 KiB

doll

// EXPLOSION!
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define cont continue
//#define endl '\n'
//#define ednl '\n'
#define test int testc;cin>>testc;while(testc--)
#define pr(a, b) trav(x,a)cerr << x << b; cerr << endl;
#define message cout << "Hello World" << endl;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 998244353;//  1000000007
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	if (sz(s))
	{
		freopen((s + ".in").c_str(), "r", stdin);
		if (s != "test1")
			freopen((s + ".out").c_str(), "w", stdout);
	}
}

#ifndef arwaeystoamneg
#include "doll.h"
#endif
#ifdef arwaeystoamneg
namespace {

    constexpr int P_MAX = 20000000;
    constexpr int S_MAX = 400000;

    int M, N;
    std::vector<int> A;

    bool answered;
    int S;
    std::vector<int> IC, IX, IY;

    int read_int() {
        int x;
        if (scanf("%d", &x) != 1) {
            fprintf(stderr, "Error while reading input\n");
            exit(1);
        }
        return x;
    }

    void wrong_answer(const char* MSG) {
        printf("Wrong Answer: %s\n", MSG);
        exit(0);
    }

    void simulate() {
        if (S > S_MAX) {
            char str[50];
            sprintf(str, "over %d switches", S_MAX);
            wrong_answer(str);
        }
        for (int i = 0; i <= M; ++i) {
            if (!(-S <= IC[i] && IC[i] <= M)) {
                wrong_answer("wrong serial number");
            }
        }
        for (int j = 1; j <= S; ++j) {
            if (!(-S <= IX[j - 1] && IX[j - 1] <= M)) {
                wrong_answer("wrong serial number");
            }
            if (!(-S <= IY[j - 1] && IY[j - 1] <= M)) {
                wrong_answer("wrong serial number");
            }
        }

        int P = 0;
        std::vector<bool> state(S + 1, false);
        int pos = IC[0];
        int k = 0;
        FILE* file_log = fopen("log.txt", "w");
        fprintf(file_log, "0\n");
        for (;;) {
            fprintf(file_log, "%d\n", pos);
            if (pos < 0) {
                if (++P > P_MAX) {
                    fclose(file_log);
                    char str[50];
                    sprintf(str, "over %d inversions", P_MAX);
                    wrong_answer(str);
                }
                state[-pos] = !state[-pos];
                pos = state[-pos] ? IX[-(1 + pos)] : IY[-(1 + pos)];
            }
            else {
                if (pos == 0) {
                    break;
                }
                if (k >= N) {
                    fclose(file_log);
                    wrong_answer("wrong motion");
                }
                if (pos != A[k++]) {
                    fclose(file_log);
                    wrong_answer("wrong motion");
                }
                pos = IC[pos];
            }
        }
        fclose(file_log);
        if (k != N) {
            wrong_answer("wrong motion");
        }
        for (int j = 1; j <= S; ++j) {
            if (state[j]) {
                wrong_answer("state 'Y'");
            }
        }
        printf("Accepted: %d %d\n", S, P);
    }

}  // namespace
void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y) {
    if (answered) {
        wrong_answer("answered not exactly once");
    }
    answered = true;
    // check if input format is correct
    if ((int)C.size() != M + 1) {
        wrong_answer("wrong array length");
    }
    if (X.size() != Y.size()) {
        wrong_answer("wrong array length");
    }
    S = X.size();
    IC = C;
    IX = X;
    IY = Y;
}
#endif
int n, m;
vi a, ans;
const int MAX = 4e5;
int x[MAX], y[MAX];
int cur = 1;
void solve(int i, vi& a)
{
    if (sz(a) == 0)return;
    if (sz(a) == 1)
    {
        x[i] = i;
        y[i] = -a[0] - 1;
        return;
    }
    vi t1, t2;
    F0R(i, sz(a))if (i & 1)t2.pb(a[i]); else t1.pb(a[i]);
    if (sz(a) % 2 == 0)
    {
        x[i] = cur;
        solve(cur++, t1);
        y[i] = cur;
        solve(cur++, t2);
        return;
    }
    x[i] = cur;
    y[cur] = i;
    x[cur] = cur + 1;
    cur++;
    solve(cur, t2);
    y[i] = cur;
    solve(cur++, t1);
}
void create_circuit(int M, std::vector<int> A) {
    m = M;
    n = sz(A);
    a = A;
    ans.rsz(m + 1);
    ans[0] = a[0];
    vector<vi>adj(m);
    F0R(i, n - 1)
    {
        adj[a[i] - 1].pb(a[i + 1] - 1);
    }
    adj[a[n - 1] - 1].pb(-1);
    F0R(i, m)
    {
        if (sz(adj[i]) == 0)continue;
        if (sz(adj[i]) == 1)
        {
            ans[i + 1] = adj[i][0] + 1;
            continue;
        }
        ans[i + 1] = -cur;
        solve(cur++, adj[i]);
    }
    vi t1, t2;
    FOR(i, 1, cur)t1.pb(-x[i]), t2.pb(-y[i]);
    answer(ans, t1, t2);
}
#ifdef arwaeystoamneg

int main() {
    setIO("test1");
    M = read_int();
    N = read_int();
    A.resize(N);
    for (int k = 0; k < N; ++k) {
        A[k] = read_int();
    }

    answered = false;
    create_circuit(M, A);
    if (!answered) {
        wrong_answer("answered not exactly once");
    }
    for (int i = 0; i <= M; ++i) {
        cout << IC[i] << " ";
    }
    cout << endl;
    for (int j = 1; j <= S; ++j) {
        cout << IX[j - 1] << " " << IY[j - 1] << endl;
    }
    cout << endl;
    simulate();
    return 0;
}
#endif

Compilation message (stderr)

doll.cpp: In function 'void setIO(std::string)':
doll.cpp:49:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   freopen((s + ".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
doll.cpp:51:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |    freopen((s + ".out").c_str(), "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 0 / 4
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 18
• Subtask 6: 0 / 56