oj.uz

Submission #413079

# Submission time Handle Problem Language Result Execution time Memory
413079 2021-05-28T08:08:55 Z usachevd0 Mechanical Doll (IOI18_doll) C++14
100 / 100
 166 ms 13068 KB 
#include <bits/stdc++.h>
#ifndef LOCAL
    #include "doll.h"
#endif

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
    return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
    return y > x ? (x = y, true) : false;
}
void debug_out() {
    cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
    cerr << ' ' << A;
    debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
    for (int i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}
#ifdef LOCAL
    #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
    #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
    #define debug(...) 1337
    #define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
    for (auto& x : v)
        stream << x << ' ';
    return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << ' ' << p.second;
}

const int INF32 = 1e9;
const int maxN = 4e5;
int X[maxN], Y[maxN];
int st[maxN];
int ord[maxN], pos[maxN];

void answer(std::vector<int> C, std::vector<int> X, std::vector<int> Y);
void create_circuit(int m, vector<int> a) {
    int n = a.size();
    a.push_back(0);
    int S = 0;
    auto newSwitch = [&]() -> int {
        ++S;
        return -S;
    };
    
    vector<int> b(n + 1);
    iota(all(b), 0);
    while (b.size() > 1) {
        if (b.size() & 1) {
            int last = b.back();
            b.pop_back();
            b.push_back(INF32);
            b.push_back(last);
        }
        vector<int> new_b;
        for (int i = 0; i < b.size(); i += 2) {
            int s = newSwitch();
            int sid = -s - 1;
            X[sid] = b[i];
            Y[sid] = b[i + 1];
            new_b.push_back(s);
        }
        swap(b, new_b);
    }
    int root = b[0];
    for (int s = 0; s < S; ++s) {
        if (X[s] == INF32) X[s] = root;
        if (Y[s] == INF32) Y[s] = root;
    }
    
    int vis = 0;
    int v = root;
    while (vis < n + 1) {
        if (v < 0) {
            int sid = -v - 1;
            if (!st[sid]) {
                v = X[sid];
            } else {
                v = Y[sid];
            }
            st[sid] ^= 1;
        } else {
            pos[v] = vis;
            ++vis;
            v = root;
        }
    }
    // mdebug(pos, m + 1);
    // mdebug(X, S);
    // mdebug(Y, S);
    for (int s = 0; s < S; ++s) {
        if (X[s] >= 0) {
            X[s] = a[pos[X[s]]];
        }
        if (Y[s] >= 0) {
            Y[s] = a[pos[Y[s]]];
        }
    }
    vector<int> x(S), y(S);
    for (int i = 0; i < S; ++i) {
        x[i] = X[i];
        y[i] = Y[i];
    }
    // debug(root);
    // debug(x);
    // debug(y);
    answer(vector<int>(m + 1, root), x, y);
}



#ifdef LOCAL

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);
}

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() {
    #ifdef LOCAL
     freopen("in", "r", stdin);
 #endif
  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;
}


// int32_t main() {
// #ifdef LOCAL
//     freopen("in", "r", stdin);
// #endif
//     ios::sync_with_stdio(0);
//     cin.tie(0);
    
    

//     return 0;
// }
#endif

Compilation message

doll.cpp: In function 'void create_circuit(int, std::vector<int>)':
doll.cpp:81:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int i = 0; i < b.size(); i += 2) {
      |                         ~~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 5436 KB Output is correct
3 Correct 56 ms 5088 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1100 KB Output is correct
6 Correct 71 ms 7440 KB Output is correct
7 Correct 1 ms 204 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 5436 KB Output is correct
3 Correct 56 ms 5088 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1100 KB Output is correct
6 Correct 71 ms 7440 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 95 ms 8640 KB Output is correct
9 Correct 101 ms 9332 KB Output is correct
10 Correct 166 ms 13068 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 48 ms 5436 KB Output is correct
3 Correct 56 ms 5088 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 13 ms 1100 KB Output is correct
6 Correct 71 ms 7440 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 95 ms 8640 KB Output is correct
9 Correct 101 ms 9332 KB Output is correct
10 Correct 166 ms 13068 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 2 ms 204 KB Output is correct
14 Correct 155 ms 12556 KB Output is correct
15 Correct 85 ms 8116 KB Output is correct
16 Correct 133 ms 12300 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 153 ms 12908 KB Output is correct
21 Correct 2 ms 204 KB Output is correct
22 Correct 2 ms 204 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 3 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 2 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 88 ms 7108 KB Output is correct
3 Correct 77 ms 7664 KB Output is correct
4 Correct 119 ms 10800 KB Output is correct

Subtask #6
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 88 ms 7108 KB Output is correct
3 Correct 77 ms 7664 KB Output is correct
4 Correct 119 ms 10800 KB Output is correct
5 Correct 157 ms 12172 KB Output is correct
6 Correct 129 ms 11780 KB Output is correct
7 Correct 125 ms 11940 KB Output is correct
8 Correct 119 ms 11552 KB Output is correct
9 Correct 83 ms 7072 KB Output is correct
10 Correct 118 ms 11524 KB Output is correct
11 Correct 128 ms 11124 KB Output is correct
12 Correct 87 ms 7904 KB Output is correct
13 Correct 79 ms 7812 KB Output is correct
14 Correct 80 ms 8192 KB Output is correct
15 Correct 81 ms 8256 KB Output is correct
16 Correct 4 ms 460 KB Output is correct
17 Correct 75 ms 7872 KB Output is correct
18 Correct 76 ms 7356 KB Output is correct
19 Correct 76 ms 7908 KB Output is correct
20 Correct 116 ms 12112 KB Output is correct
21 Correct 142 ms 11148 KB Output is correct
22 Correct 139 ms 11148 KB Output is correct