oj.uz

Submission #259479

# Submission time Handle Problem Language Result Execution time Memory
259479 2020-08-07T22:02:30 Z Bruteforceman Stray Cat (JOI20_stray) C++17
15 / 100
 90 ms 16884 KB 
#include "bits/stdc++.h"
#include "Anthony.h"
using namespace std;

namespace {
  const int maxn = 2e4 + 10;
  const int t[] = {1, 0, 0, 1, 1, 0};
  const int len = 6;
  int l[maxn], r[maxn];
  int dist[maxn];
  vector <int> g[maxn];
  int mark[maxn];

  void dfs(int x, int par, int idx) {
    int child = 0;
    for(auto e : g[x]) {
      if(e != par) {
        child += 1; 
      }
    }
    if(child == 1 && idx == -1) {
      for(idx = 0; idx < len; idx++) {
        if(t[idx] == mark[x]) {
          break;
        }
      }
    }
    for(auto e : g[x]) {
      int i = l[e] ^ r[e] ^ x; 
      if(e != par) {
        if(child == 1) {
          mark[e] = t[(idx + 1) % len];
          dfs(i, e, (idx + 1) % len);
        } else {
          mark[e] = mark[par] ^ 1;
          dfs(i, e, -1);
        }
      }
    }
  }
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  std::vector<int> X(M);
  for (int i = 0; i < N; i++) g[i].clear();
  for (int i = 0; i < M; ++i) {
    l[i] = U[i];
    r[i] = V[i];
    g[l[i]].push_back(i);
    g[r[i]].push_back(i);
  }
  if(A > 2) {
    for(int i = 0; i < N; i++) dist[i] = -1;
    queue <int> Q;
    Q.push(0);
    dist[0] = 0;
    while(!Q.empty()) {
      int x = Q.front();
      Q.pop();
      for(int e : g[x]) {
        int i = l[e] ^ r[e] ^ x;
        if(dist[i] == -1) {
          dist[i] = 1 + dist[x];
          Q.push(i);
        }
      }
    }
    for(int i = 0; i < M; i++) {
      if(dist[l[i]] == dist[r[i]]) X[i] = dist[l[i]] % 3;
      else X[i] = min(dist[l[i]], dist[r[i]]) % 3;
    }
    return X;
  }
  mark[M] = 0;
  dfs(0, M, -1);
  for(int i = 0; i < M; i++) X[i] = mark[i];
  return X;
}

#include "bits/stdc++.h"
#include "Catherine.h"
using namespace std;

namespace {
const int len = 6;
const int t[len] = {1, 0, 0, 1, 1, 0};
int arr[len];
int idx = -1;

int A, B;
int variable_example = 0;
vector <int> unpack(vector <int> y) {
  vector <int> v;
  for(int i = 0; i < y.size(); i++) {
    while(y[i]--) v.push_back(i);
  }
  return v;
}
bool check() {
  arr[len - 1] = 1;
  for(int i = 0; i < len - 1; i++) arr[len - 1] ^= arr[i];
  for(int i = 0; i < len; i++) {
    bool bad = false;
    for(int j = 0; j < len; j++) {
      if(t[(i + j) % len] != arr[j]) bad = true;
    }
    if(not bad) return true;
  }
  return false;
}
int last = -1;
}  // namespace

void Init(int A, int B) {
  ::A = A;
  ::B = B;
}

int Move(std::vector<int> y) {
  if(A > 2) {
    for(int i = 0; i < 3; i++) {
      if(y[i] > 0 && y[(2 + i) % 3] == 0) return i;
    }
  }
  ++variable_example;
  vector <int> v = unpack(y);
  if(variable_example == 1 && v.size() == 2) {
    idx = 1; 
    arr[idx - 1] = v[0];
    arr[idx] = v[1];
    return last = v[1];
  }
  if(idx != -1) {
    if(v.size() == 1) {
      arr[idx + 1] = v[0];
      idx += 1;
      if(idx == len - 2) {
        idx = -1;
        if(check()) return -1;
        else return last = v[0];
      } else {
        return last = v[0];
      }
    } else {
      idx = -1;
      if(y[0] == 0 || y[1] == 0) return -1;
      else return last = last ^ 1;
    }
  }
  if(v.size() == 1) return last = v[0];
  else if(last == -1) {
    for(int i = 0; i < y.size(); i++) if(y[i] == 1) return last = i;
  }
  else return last = last ^ 1;
}

Compilation message

Catherine.cpp: In function 'std::vector<int> {anonymous}::unpack(std::vector<int>)':
Catherine.cpp:15:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < y.size(); i++) {
                  ~~^~~~~~~~~~
Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:73:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < y.size(); i++) if(y[i] == 1) return last = i;
                    ~~^~~~~~~~~~
Catherine.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15732 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 44 ms 15096 KB Output is correct
4 Correct 71 ms 16780 KB Output is correct
5 Correct 90 ms 16884 KB Output is correct
6 Correct 61 ms 15592 KB Output is correct
7 Correct 52 ms 15476 KB Output is correct
8 Correct 67 ms 16244 KB Output is correct
9 Correct 64 ms 16248 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 15732 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 44 ms 15096 KB Output is correct
4 Correct 71 ms 16780 KB Output is correct
5 Correct 90 ms 16884 KB Output is correct
6 Correct 61 ms 15592 KB Output is correct
7 Correct 52 ms 15476 KB Output is correct
8 Correct 67 ms 16244 KB Output is correct
9 Correct 64 ms 16248 KB Output is correct
10 Correct 44 ms 13552 KB Output is correct
11 Correct 54 ms 13548 KB Output is correct
12 Correct 53 ms 13548 KB Output is correct
13 Correct 50 ms 13552 KB Output is correct
14 Correct 50 ms 13868 KB Output is correct
15 Correct 51 ms 14260 KB Output is correct
16 Correct 60 ms 16380 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13388 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 44 ms 12916 KB Output is correct
4 Correct 66 ms 14780 KB Output is correct
5 Correct 57 ms 14716 KB Output is correct
6 Correct 50 ms 13300 KB Output is correct
7 Correct 45 ms 13164 KB Output is correct
8 Correct 67 ms 14068 KB Output is correct
9 Correct 55 ms 14148 KB Output is correct
10 Correct 56 ms 13812 KB Output is correct
11 Correct 56 ms 13692 KB Output is correct
12 Correct 49 ms 13892 KB Output is correct
13 Correct 50 ms 13684 KB Output is correct
14 Correct 57 ms 14280 KB Output is correct
15 Correct 58 ms 14164 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 13388 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 44 ms 12916 KB Output is correct
4 Correct 66 ms 14780 KB Output is correct
5 Correct 57 ms 14716 KB Output is correct
6 Correct 50 ms 13300 KB Output is correct
7 Correct 45 ms 13164 KB Output is correct
8 Correct 67 ms 14068 KB Output is correct
9 Correct 55 ms 14148 KB Output is correct
10 Correct 56 ms 13812 KB Output is correct
11 Correct 56 ms 13692 KB Output is correct
12 Correct 49 ms 13892 KB Output is correct
13 Correct 50 ms 13684 KB Output is correct
14 Correct 57 ms 14280 KB Output is correct
15 Correct 58 ms 14164 KB Output is correct
16 Correct 41 ms 11832 KB Output is correct
17 Correct 43 ms 11836 KB Output is correct
18 Correct 44 ms 11660 KB Output is correct
19 Correct 45 ms 11676 KB Output is correct
20 Correct 53 ms 12260 KB Output is correct
21 Correct 46 ms 12024 KB Output is correct
22 Correct 57 ms 14288 KB Output is correct
23 Correct 50 ms 11920 KB Output is correct
24 Correct 48 ms 11796 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1792 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 2 ms 1792 KB Output is correct
4 Correct 2 ms 1792 KB Output is correct
5 Correct 2 ms 1792 KB Output is correct
6 Correct 2 ms 1792 KB Output is correct
7 Correct 3 ms 2048 KB Output is correct
8 Correct 2 ms 1792 KB Output is correct
9 Correct 2 ms 1792 KB Output is correct
10 Correct 2 ms 1792 KB Output is correct
11 Correct 3 ms 1792 KB Output is correct
12 Correct 2 ms 1792 KB Output is correct
13 Correct 2 ms 1792 KB Output is correct
14 Correct 2 ms 1792 KB Output is correct
15 Correct 2 ms 1792 KB Output is correct
16 Correct 2 ms 1792 KB Output is correct
17 Correct 2 ms 1792 KB Output is correct
18 Correct 3 ms 1792 KB Output is correct
19 Correct 2 ms 1792 KB Output is correct
20 Correct 2 ms 1792 KB Output is correct
21 Correct 2 ms 1792 KB Output is correct
22 Correct 2 ms 1792 KB Output is correct
23 Correct 2 ms 1792 KB Output is correct
24 Correct 2 ms 1792 KB Output is correct
25 Correct 2 ms 1792 KB Output is correct
26 Incorrect 2 ms 1792 KB Wrong Answer [5]
27 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 11428 KB Output is correct
2 Correct 52 ms 12540 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 36 ms 11128 KB Output is correct
5 Correct 60 ms 14200 KB Output is correct
6 Correct 57 ms 14284 KB Output is correct
7 Correct 48 ms 13468 KB Output is correct
8 Correct 46 ms 13512 KB Output is correct
9 Correct 56 ms 14204 KB Output is correct
10 Correct 55 ms 14260 KB Output is correct
11 Correct 58 ms 14388 KB Output is correct
12 Correct 58 ms 14180 KB Output is correct
13 Correct 56 ms 14280 KB Output is correct
14 Correct 60 ms 14312 KB Output is correct
15 Correct 57 ms 14272 KB Output is correct
16 Correct 61 ms 14260 KB Output is correct
17 Correct 68 ms 13940 KB Output is correct
18 Correct 54 ms 14068 KB Output is correct
19 Correct 56 ms 13956 KB Output is correct
20 Correct 53 ms 13948 KB Output is correct
21 Correct 57 ms 13940 KB Output is correct
22 Correct 63 ms 14004 KB Output is correct
23 Correct 45 ms 11380 KB Output is correct
24 Correct 46 ms 11456 KB Output is correct
25 Correct 54 ms 12144 KB Output is correct
26 Correct 46 ms 12144 KB Output is correct
27 Correct 52 ms 12856 KB Output is correct
28 Correct 52 ms 12660 KB Output is correct
29 Correct 50 ms 12828 KB Output is correct
30 Correct 51 ms 12832 KB Output is correct
31 Correct 41 ms 11516 KB Output is correct
32 Correct 44 ms 11568 KB Output is correct
33 Correct 43 ms 11900 KB Output is correct
34 Correct 44 ms 12144 KB Output is correct
35 Correct 50 ms 12660 KB Output is correct
36 Correct 50 ms 12552 KB Output is correct
37 Correct 52 ms 12412 KB Output is correct
38 Correct 51 ms 12756 KB Output is correct
39 Correct 51 ms 12640 KB Output is correct
40 Correct 50 ms 12636 KB Output is correct
41 Correct 53 ms 13308 KB Output is correct
42 Correct 54 ms 13328 KB Output is correct
43 Correct 54 ms 13172 KB Output is correct
44 Correct 53 ms 13180 KB Output is correct
45 Correct 53 ms 13204 KB Output is correct
46 Correct 54 ms 13308 KB Output is correct
47 Correct 50 ms 12532 KB Output is correct
48 Correct 49 ms 12404 KB Output is correct
49 Correct 48 ms 12388 KB Output is correct
50 Correct 48 ms 12748 KB Output is correct
51 Correct 43 ms 11644 KB Output is correct
52 Correct 45 ms 12012 KB Output is correct
53 Correct 45 ms 11644 KB Output is correct
54 Correct 43 ms 11856 KB Output is correct
55 Correct 45 ms 11940 KB Output is correct
56 Correct 53 ms 11636 KB Output is correct
57 Correct 47 ms 11516 KB Output is correct
58 Correct 50 ms 11600 KB Output is correct
59 Incorrect 50 ms 11644 KB Wrong Answer [5]
60 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 11428 KB Output is correct
2 Correct 49 ms 12608 KB Output is correct
3 Correct 1 ms 1536 KB Output is correct
4 Correct 39 ms 11264 KB Output is correct
5 Correct 57 ms 14196 KB Output is correct
6 Correct 57 ms 14268 KB Output is correct
7 Correct 57 ms 13376 KB Output is correct
8 Correct 45 ms 13496 KB Output is correct
9 Correct 65 ms 14388 KB Output is correct
10 Correct 63 ms 14304 KB Output is correct
11 Correct 67 ms 14388 KB Output is correct
12 Correct 63 ms 14372 KB Output is correct
13 Correct 63 ms 14344 KB Output is correct
14 Correct 56 ms 14204 KB Output is correct
15 Correct 56 ms 14388 KB Output is correct
16 Correct 57 ms 14196 KB Output is correct
17 Correct 53 ms 13812 KB Output is correct
18 Correct 54 ms 14084 KB Output is correct
19 Correct 54 ms 14636 KB Output is correct
20 Correct 56 ms 14536 KB Output is correct
21 Correct 60 ms 14420 KB Output is correct
22 Correct 55 ms 14488 KB Output is correct
23 Incorrect 41 ms 11756 KB Wrong Answer [5]
24 Halted 0 ms 0 KB -