oj.uz

답안 #600662

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
600662 2022-07-21T06:43:43 Z cadmiumsky 길고양이 (JOI20_stray) C++14
15 / 100
 59 ms 16444 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 = -1;
  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

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 15408 KB Output is correct
2 Correct 1 ms 1036 KB Output is correct
3 Correct 33 ms 14724 KB Output is correct
4 Correct 50 ms 16408 KB Output is correct
5 Correct 44 ms 16444 KB Output is correct
6 Correct 35 ms 15224 KB Output is correct
7 Correct 35 ms 15156 KB Output is correct
8 Correct 43 ms 15920 KB Output is correct
9 Correct 43 ms 15964 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 15408 KB Output is correct
2 Correct 1 ms 1036 KB Output is correct
3 Correct 33 ms 14724 KB Output is correct
4 Correct 50 ms 16408 KB Output is correct
5 Correct 44 ms 16444 KB Output is correct
6 Correct 35 ms 15224 KB Output is correct
7 Correct 35 ms 15156 KB Output is correct
8 Correct 43 ms 15920 KB Output is correct
9 Correct 43 ms 15964 KB Output is correct
10 Correct 41 ms 13336 KB Output is correct
11 Correct 34 ms 13400 KB Output is correct
12 Correct 34 ms 13332 KB Output is correct
13 Correct 32 ms 13200 KB Output is correct
14 Correct 32 ms 13644 KB Output is correct
15 Correct 43 ms 14008 KB Output is correct
16 Correct 44 ms 15900 KB Output is correct

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 12964 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 38 ms 12616 KB Output is correct
4 Correct 59 ms 14224 KB Output is correct
5 Correct 47 ms 14260 KB Output is correct
6 Correct 37 ms 12968 KB Output is correct
7 Correct 35 ms 13024 KB Output is correct
8 Correct 39 ms 13592 KB Output is correct
9 Correct 40 ms 13616 KB Output is correct
10 Correct 46 ms 13308 KB Output is correct
11 Correct 38 ms 13352 KB Output is correct
12 Correct 37 ms 13388 KB Output is correct
13 Correct 36 ms 13336 KB Output is correct
14 Correct 45 ms 13584 KB Output is correct
15 Correct 53 ms 13652 KB Output is correct

Subtask #4
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 12964 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct
3 Correct 38 ms 12616 KB Output is correct
4 Correct 59 ms 14224 KB Output is correct
5 Correct 47 ms 14260 KB Output is correct
6 Correct 37 ms 12968 KB Output is correct
7 Correct 35 ms 13024 KB Output is correct
8 Correct 39 ms 13592 KB Output is correct
9 Correct 40 ms 13616 KB Output is correct
10 Correct 46 ms 13308 KB Output is correct
11 Correct 38 ms 13352 KB Output is correct
12 Correct 37 ms 13388 KB Output is correct
13 Correct 36 ms 13336 KB Output is correct
14 Correct 45 ms 13584 KB Output is correct
15 Correct 53 ms 13652 KB Output is correct
16 Correct 35 ms 11584 KB Output is correct
17 Correct 28 ms 11492 KB Output is correct
18 Correct 30 ms 11492 KB Output is correct
19 Correct 32 ms 11448 KB Output is correct
20 Correct 41 ms 12108 KB Output is correct
21 Correct 36 ms 11872 KB Output is correct
22 Correct 43 ms 13888 KB Output is correct
23 Correct 39 ms 11528 KB Output is correct
24 Correct 34 ms 11588 KB Output is correct

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 1284 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# 결과 실행 시간 메모리 Grader output
1 Correct 35 ms 11156 KB Output is correct
2 Incorrect 35 ms 12432 KB Wrong Answer [3]
3 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 28 ms 11164 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -