oj.uz

Submission #600645

# Submission time Handle Problem Language Result Execution time Memory
600645 2022-07-21T06:39:49 Z cadmiumsky Stray Cat (JOI20_stray) C++14
15 / 100
 68 ms 16960 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

const int nmax = 2e4 + 5;
using pii = pair<int,int>;
vector<int> rez;

namespace {
  #define F nustiusacompilezcodurilol
  const string F[2] = {"011001", "100101"};
  vector<pii> g[nmax];
  int p[nmax];
  void dfs(int node, int f = 0, int toggle = -1, int state = -1) {
    if(g[node].size() - (node != f) == 1) {
      if(state == -1) {
        toggle = p[node];
        state = 1;
      }
      else
        state = (state + 1) % 6;
    }
    else 
      state = -1;
    for(int i = 0; i < g[node].size(); i++) {    
      int x, e;
      tie(e, x) = g[node][i];
      if(x == f)
        swap(g[node][i], g[node].back()),
        g[node].pop_back(),
        i--;
      else {
        if(state == -1)
          rez[e] = p[node] ^ 1;
        else 
          rez[e] = F[toggle][state] - '0';    
        p[x] = rez[e];
        dfs(x, node, toggle, state);
      }
    }
    return;
  }
}  // namespace

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V) {
  rez.resize(M, -1);
  for (int i = 0; i < M; ++i) {
    g[U[i]].emplace_back(i, V[i]);
    g[V[i]].emplace_back(i, U[i]);
  }
  if(A > 2) {
    queue<int> que;
    vector<int> occ(N, 0);
    que.push(0);
    occ[0] = 3;
    while(!que.empty()) {
      int node = que.front(), mine = occ[node] - 1;
      //cerr << node << ' ' << occ[node] << '\n';
      que.pop();
      for(auto [e, x] : g[node]) {
        rez[e] = rez[e] == -1? (mine + 1) % 3 : rez[e];
        if(occ[x] == 0) {
          occ[x] = rez[e] + 1;
          que.push(x);
        } 
      }
    }
    //for(int i = 0; i < M; i++) {
      //cerr << rez[i] << ' ' << U[i] << ' ' << V[i] << '\n';
    //}
  }
  else
    dfs(0);
  return rez;
}
#undef F

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

namespace {
  const string F[2] = {"011001", "100101"};

  int A, B;
  int variable_example = 0;
  unordered_set<string> goodstrings;
  void initgs() {
    string s = F[0] + F[0], t = F[1] + F[1];
    int n = F[0].size();
    for(int i = 0; i < n; i++) {
      goodstrings.insert(s.substr(i, 5));
      goodstrings.insert(t.substr(i, 5));
    }
    return;
  }
  int timer, lastval = -1;
  int state = 0;
  string curr = "";
  int gsum(vector<int> v) { return accumulate(v.begin(), v.end(), 0); }

} 
int amogii = -1;
// 0 - 1 - 1 - 0 - 0 - 1 - 0 - 1 - 1 - 0 - 0 - 1 - 0 - 1 - 1 - 0 - 0 - 1 -

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

int Move(std::vector<int> v) {
  int sum = gsum(v);
  if(A == 2) {
    if(state == -1) {
      if(sum == 0)
        return -1; // ???
      else if(sum == 1) {
        if(v[0] == 1) return lastval = 0;
        return lastval = 1;
      }
      else
        return lastval ^= 1;
    }
    if(state == 0) {
      if(sum == 1) {
        int ptr = 0;
        for(int i = 0; i < A; i++)
          if(v[i] == 0) {
            lastval = i;
            break;
          }
        state = -1;
        return lastval;
      }
      if(sum == 2) {
        state = 1;
        if(v[1] == 0) {
          curr = "00";
          return lastval = 0;
        }
        if(v[1] == 1) {
          curr = "01";
          return lastval = 1;
        }
        curr = "11";
        return lastval = 1;
      }
      else {
        for(int i = 0; i < A; i++)
          if(v[i] == 1) {
            lastval = i;
            break;
          }
        state = -1;
        return lastval;
      }
    }
    if(state <= 3) {
      if(sum == 0) {
        state = -1;
        return -1;
      }
      if(sum > 1) {
        state = -1;
        if(v[lastval] == 0) {
          return -1;
        }
        return lastval ^= 1;
      }
      else {
        if(v[0] == 1) curr += '0';
        else curr += '1';
        if(state == 3) {
          state = -1;
          if(goodstrings.count(curr))
            return lastval = curr.back() - '0';
          return -1;
        }
        else {
          state++;
          return lastval = curr.back() - '0';
        }
      }
    }
    return -1;
  }
  else {
    int cnt = 0;
    for(auto x : v)
      if(x != 0)
        cnt++;
    if(cnt == 0)
      return -1;
    else if(cnt == 1) {
      if(v[0] != 0) return 0;
      if(v[1] != 0) return 1;
      if(v[2] != 0) return 2;
      //for(auto x : v)
        //cerr << x << ' ';
      //cerr << '\n';
    }
    else { // X --0-- Y --1-- Z --2-- T --0-- U
      if(v[0] == 0) return 1;
      if(v[1] == 0) return 2;
      if(v[2] == 0) return 0;
    }
    while(1);
  }
}

Compilation message

Anthony.cpp: In function 'void {anonymous}::dfs(int, int, int, int)':
Anthony.cpp:25:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int i = 0; i < g[node].size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:61:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |       for(auto [e, x] : g[node]) {
      |                ^

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:50:13: warning: unused variable 'ptr' [-Wunused-variable]
   50 |         int ptr = 0;
      |             ^~~
Catherine.cpp: At global scope:
Catherine.cpp:20:7: warning: '{anonymous}::timer' defined but not used [-Wunused-variable]
   20 |   int timer, lastval = -1;
      |       ^~~~~
Catherine.cpp:9:7: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    9 |   int variable_example = 0;
      |       ^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 15788 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 32 ms 15112 KB Output is correct
4 Correct 68 ms 16960 KB Output is correct
5 Correct 64 ms 16756 KB Output is correct
6 Correct 47 ms 15588 KB Output is correct
7 Correct 45 ms 15500 KB Output is correct
8 Correct 49 ms 16404 KB Output is correct
9 Correct 61 ms 16292 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 15788 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 32 ms 15112 KB Output is correct
4 Correct 68 ms 16960 KB Output is correct
5 Correct 64 ms 16756 KB Output is correct
6 Correct 47 ms 15588 KB Output is correct
7 Correct 45 ms 15500 KB Output is correct
8 Correct 49 ms 16404 KB Output is correct
9 Correct 61 ms 16292 KB Output is correct
10 Correct 39 ms 13784 KB Output is correct
11 Correct 39 ms 13680 KB Output is correct
12 Correct 56 ms 13676 KB Output is correct
13 Correct 44 ms 13788 KB Output is correct
14 Correct 47 ms 13984 KB Output is correct
15 Correct 63 ms 14364 KB Output is correct
16 Correct 48 ms 16460 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 13376 KB Output is correct
2 Correct 2 ms 1052 KB Output is correct
3 Correct 35 ms 12904 KB Output is correct
4 Correct 60 ms 14648 KB Output is correct
5 Correct 55 ms 14708 KB Output is correct
6 Correct 53 ms 13364 KB Output is correct
7 Correct 54 ms 13428 KB Output is correct
8 Correct 54 ms 14052 KB Output is correct
9 Correct 57 ms 13972 KB Output is correct
10 Correct 51 ms 13808 KB Output is correct
11 Correct 52 ms 13796 KB Output is correct
12 Correct 57 ms 13804 KB Output is correct
13 Correct 54 ms 13840 KB Output is correct
14 Correct 65 ms 14060 KB Output is correct
15 Correct 63 ms 13964 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 13376 KB Output is correct
2 Correct 2 ms 1052 KB Output is correct
3 Correct 35 ms 12904 KB Output is correct
4 Correct 60 ms 14648 KB Output is correct
5 Correct 55 ms 14708 KB Output is correct
6 Correct 53 ms 13364 KB Output is correct
7 Correct 54 ms 13428 KB Output is correct
8 Correct 54 ms 14052 KB Output is correct
9 Correct 57 ms 13972 KB Output is correct
10 Correct 51 ms 13808 KB Output is correct
11 Correct 52 ms 13796 KB Output is correct
12 Correct 57 ms 13804 KB Output is correct
13 Correct 54 ms 13840 KB Output is correct
14 Correct 65 ms 14060 KB Output is correct
15 Correct 63 ms 13964 KB Output is correct
16 Correct 44 ms 11828 KB Output is correct
17 Correct 44 ms 11804 KB Output is correct
18 Correct 38 ms 11896 KB Output is correct
19 Correct 40 ms 11872 KB Output is correct
20 Correct 48 ms 12496 KB Output is correct
21 Correct 52 ms 12136 KB Output is correct
22 Correct 56 ms 14096 KB Output is correct
23 Correct 43 ms 11940 KB Output is correct
24 Correct 45 ms 11976 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1268 KB Output is correct
2 Correct 2 ms 1028 KB Output is correct
3 Correct 2 ms 1392 KB Output is correct
4 Incorrect 2 ms 1424 KB Wrong Answer [5]
5 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 11612 KB Wrong Answer [5]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 11572 KB Output is correct
2 Correct 57 ms 12756 KB Output is correct
3 Incorrect 2 ms 1080 KB Wrong Answer [5]
4 Halted 0 ms 0 KB -