oj.uz

Submission #600396

# Submission time Handle Problem Language Result Execution time Memory
600396 2022-07-20T19:53:13 Z cadmiumsky Stray Cat (JOI20_stray) C++14
4 / 100
 54 ms 24704 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] == 1) return 0;
      if(v[1] == 1) return 1;
      if(v[2] == 1) return 2;
      //for(auto x : v)
        //cerr << x << ' ';
      //cerr << '\n';
      assert(amogii == 0);
    }
    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;
    }
    assert(false);
  }
}

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 36 ms 15472 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 30 ms 15168 KB Output is correct
4 Correct 45 ms 16880 KB Output is correct
5 Correct 54 ms 16840 KB Output is correct
6 Correct 39 ms 15612 KB Output is correct
7 Correct 36 ms 15700 KB Output is correct
8 Correct 40 ms 16292 KB Output is correct
9 Correct 41 ms 16364 KB Output is correct

Subtask #2
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15472 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 30 ms 15168 KB Output is correct
4 Correct 45 ms 16880 KB Output is correct
5 Correct 54 ms 16840 KB Output is correct
6 Correct 39 ms 15612 KB Output is correct
7 Correct 36 ms 15700 KB Output is correct
8 Correct 40 ms 16292 KB Output is correct
9 Correct 41 ms 16364 KB Output is correct
10 Correct 32 ms 13824 KB Output is correct
11 Runtime error 37 ms 24704 KB Execution killed with signal 6
12 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12944 KB Output is correct
2 Correct 2 ms 1028 KB Output is correct
3 Correct 32 ms 12816 KB Output is correct
4 Correct 44 ms 14756 KB Output is correct
5 Correct 40 ms 14720 KB Output is correct
6 Correct 37 ms 13548 KB Output is correct
7 Correct 34 ms 13416 KB Output is correct
8 Correct 41 ms 14108 KB Output is correct
9 Correct 39 ms 13988 KB Output is correct
10 Correct 37 ms 13856 KB Output is correct
11 Correct 35 ms 13904 KB Output is correct
12 Correct 40 ms 13828 KB Output is correct
13 Correct 41 ms 13904 KB Output is correct
14 Correct 39 ms 14256 KB Output is correct
15 Correct 44 ms 14104 KB Output is correct

Subtask #4
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 12944 KB Output is correct
2 Correct 2 ms 1028 KB Output is correct
3 Correct 32 ms 12816 KB Output is correct
4 Correct 44 ms 14756 KB Output is correct
5 Correct 40 ms 14720 KB Output is correct
6 Correct 37 ms 13548 KB Output is correct
7 Correct 34 ms 13416 KB Output is correct
8 Correct 41 ms 14108 KB Output is correct
9 Correct 39 ms 13988 KB Output is correct
10 Correct 37 ms 13856 KB Output is correct
11 Correct 35 ms 13904 KB Output is correct
12 Correct 40 ms 13828 KB Output is correct
13 Correct 41 ms 13904 KB Output is correct
14 Correct 39 ms 14256 KB Output is correct
15 Correct 44 ms 14104 KB Output is correct
16 Correct 33 ms 11880 KB Output is correct
17 Runtime error 32 ms 20852 KB Execution killed with signal 6
18 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1288 KB Output is correct
2 Correct 1 ms 1020 KB Output is correct
3 Correct 1 ms 1288 KB Output is correct
4 Incorrect 2 ms 1292 KB Wrong Answer [5]
5 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 11200 KB Output is correct
2 Correct 38 ms 12168 KB Output is correct
3 Incorrect 0 ms 1036 KB Wrong Answer [5]
4 Halted 0 ms 0 KB -