Submission #578417

#	Time	Username	Problem	Language	Result	Execution time	Memory
578417		Theo830	Mechanical Doll (IOI18_doll)	C++17	47 / 100	121 ms	13980 KiB

doll

    #include <bits/stdc++.h>
    using namespace std;
    typedef int ll;
    ll INF = 1e18+7;
    ll MOD = 998244353;
    typedef pair<ll,ll> ii;
    #define iii pair<ll,ii>
    #define f(i,a,b) for(ll i = a;i < b;i++)
    #define pb push_back
    #define vll vector<ll>
    #define F first
    #define S second
    #define all(x) (x).begin(), (x).end()
    ///I hope I will get uprating and don't make mistakes
    ///I will never stop programming
    ///sqrt(-1) Love C++
    ///Please don't hack me
    ///@TheofanisOrfanou Theo830
    ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
    ///Stay Calm
    ///Look for special cases
    ///Beware of overflow and array bounds
    ///Think the problem backwards
    ///Training
    #include "doll.h"
    //void create_circuit(int M, std::vector<int> A);
    //void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
    vector<int> X,Y,C;
    ll pos = 2;
    void solve(ll s,vll arr){
        if((ll)arr.size() == 1){
            X[s - 1] = -s;
            Y[s - 1] = arr[0];
            return;
        }
        if((ll)arr.size() == 2){
            X[s - 1] = arr[0];
            Y[s - 1] = arr[1];
            return;
        }
        vll exo[2];
        f(i,0,(ll)arr.size()){
            exo[i % 2].pb(arr[i]);
        }
        if((ll)arr.size() % 2){
            exo[1].pb(exo[0].back());
            exo[0].back() = -s;
            assert(exo[0].size() == exo[1].size());
        }
      	bool ola = 1;
      	for(auto x:exo[0]){
          ola &= x == 1;
        }
      	if(!ola){
          X[s - 1] = -pos;
          Y[s - 1] = -(pos + 1);
          X.pb(0);
          X.pb(0);
          Y.pb(0);
          Y.pb(0);
          pos += 2;
          solve(-X[s - 1],exo[0]);
          solve(-Y[s - 1],exo[1]);
        }
      else{
        X[s - 1] = 1;
          Y[s - 1] = -pos;
          X.pb(0);
          Y.pb(0);
          pos++;
          solve(-Y[s - 1],exo[1]);
      }
    }
    void create_circuit(int M, std::vector<int> A) {
          int n = A.size();
          X.pb(0);
          Y.pb(0);
          f(i,0,M+1){
              C.pb(-1);
          }
          C[0] = A[0];
          set<ll>ex;
          A.pb(0);
          A.erase(A.begin());
          solve(1,A);
          answer(C, X, Y);
    }
    /*
    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;
    }
     
    int main() {
      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");
      }
      FILE *file_out = fopen("out.txt", "w");
      fprintf(file_out, "%d\n", S);
      for (int i = 0; i <= M; ++i) {
        fprintf(file_out, "%d\n", IC[i]);
      }
      for (int j = 1; j <= S; ++j) {
        fprintf(file_out, "%d %d\n", IX[j - 1], IY[j - 1]);
      }
      fclose(file_out);
      simulate();
      return 0;
    }
    */

Compilation message (stderr)

doll.cpp:4:18: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
    4 |     ll INF = 1e18+7;
      |              ~~~~^~
doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:75:15: warning: unused variable 'n' [-Wunused-variable]
   75 |           int n = A.size();
      |               ^

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