oj.uz

Submission #600691

# Submission time Handle Problem Language Result Execution time Memory
600691 2022-07-21T07:06:36 Z cadmiumsky Stray Cat (JOI20_stray) C++14
15 / 100
 241 ms 17200 KB 
#include "Anthony.h"
#include <bits/stdc++.h>
using namespace std;

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

//001011 101100


namespace {
  #define F nustiusacompilezcodurilol
  const string F = "001011001011";
  vector<pii> g[nmax];
  int p[nmax];
  void dfs(int node, int f = 0, int state = -1) {
    if(g[node].size() - (node != f) == 1) {
      if(state == -1) {
        if(p[node] == 0)
          state = 1;
        else
          state = 3;
      }
      else
        state = (state + 1) % 12;
    }
    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[state] - '0';    
        p[x] = rez[e];
        dfs(x, node, 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);
    for(int i = 0; i < M; i++) {
      cerr << rez[i] << ' ' << U[i] << ' ' << V[i] << '\n';
    }
  }
  return rez;
}
#undef F

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

namespace {
  const string F = "001011001011";

  int A, B;
  int variable_example = 0;
  unordered_set<string> goodstrings;
  void initgs() {
    string s = F + F;
    reverse(s.begin(), s.end());
    int n = F.size();
    for(int i = 0; i < n; i++) {
      goodstrings.insert(s.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(lastval == -1 || sum == 1) {
        if(v[0] > 0) 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)':
Anthony.cpp:30: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]
   30 |     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:66:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   66 |       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 41 ms 15888 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 33 ms 15136 KB Output is correct
4 Correct 52 ms 17200 KB Output is correct
5 Correct 53 ms 16876 KB Output is correct
6 Correct 35 ms 15660 KB Output is correct
7 Correct 39 ms 15584 KB Output is correct
8 Correct 45 ms 16252 KB Output is correct
9 Correct 59 ms 16160 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 15888 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 33 ms 15136 KB Output is correct
4 Correct 52 ms 17200 KB Output is correct
5 Correct 53 ms 16876 KB Output is correct
6 Correct 35 ms 15660 KB Output is correct
7 Correct 39 ms 15584 KB Output is correct
8 Correct 45 ms 16252 KB Output is correct
9 Correct 59 ms 16160 KB Output is correct
10 Correct 35 ms 13804 KB Output is correct
11 Correct 41 ms 13936 KB Output is correct
12 Correct 35 ms 13768 KB Output is correct
13 Correct 32 ms 13864 KB Output is correct
14 Correct 34 ms 14112 KB Output is correct
15 Correct 37 ms 14344 KB Output is correct
16 Correct 41 ms 16328 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13636 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 35 ms 12864 KB Output is correct
4 Correct 45 ms 14648 KB Output is correct
5 Correct 46 ms 14744 KB Output is correct
6 Correct 37 ms 13472 KB Output is correct
7 Correct 37 ms 13492 KB Output is correct
8 Correct 46 ms 13996 KB Output is correct
9 Correct 39 ms 14028 KB Output is correct
10 Correct 41 ms 13800 KB Output is correct
11 Correct 37 ms 13836 KB Output is correct
12 Correct 41 ms 13856 KB Output is correct
13 Correct 46 ms 13828 KB Output is correct
14 Correct 44 ms 14028 KB Output is correct
15 Correct 39 ms 14120 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 13636 KB Output is correct
2 Correct 1 ms 1028 KB Output is correct
3 Correct 35 ms 12864 KB Output is correct
4 Correct 45 ms 14648 KB Output is correct
5 Correct 46 ms 14744 KB Output is correct
6 Correct 37 ms 13472 KB Output is correct
7 Correct 37 ms 13492 KB Output is correct
8 Correct 46 ms 13996 KB Output is correct
9 Correct 39 ms 14028 KB Output is correct
10 Correct 41 ms 13800 KB Output is correct
11 Correct 37 ms 13836 KB Output is correct
12 Correct 41 ms 13856 KB Output is correct
13 Correct 46 ms 13828 KB Output is correct
14 Correct 44 ms 14028 KB Output is correct
15 Correct 39 ms 14120 KB Output is correct
16 Correct 28 ms 11968 KB Output is correct
17 Correct 33 ms 11940 KB Output is correct
18 Correct 34 ms 11940 KB Output is correct
19 Correct 36 ms 11972 KB Output is correct
20 Correct 54 ms 12668 KB Output is correct
21 Correct 35 ms 12344 KB Output is correct
22 Correct 40 ms 14252 KB Output is correct
23 Correct 32 ms 12004 KB Output is correct
24 Correct 38 ms 12056 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1296 KB Output is correct
2 Correct 1 ms 1036 KB Output is correct
3 Correct 6 ms 1272 KB Output is correct
4 Incorrect 9 ms 1344 KB Wrong Answer [5]
5 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 11896 KB Output is correct
2 Correct 241 ms 12792 KB Output is correct
3 Incorrect 1 ms 1036 KB Wrong Answer [5]
4 Halted 0 ms 0 KB -