oj.uz

답안 #600397

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
600397 2022-07-20T19:54:00 Z cadmiumsky 길고양이 (JOI20_stray) C++14
4 / 100
 3000 ms 16572 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';
      while(1);
    }
    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 47 ms 15408 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 30 ms 14792 KB Output is correct
4 Correct 43 ms 16480 KB Output is correct
5 Correct 43 ms 16572 KB Output is correct
6 Correct 37 ms 15196 KB Output is correct
7 Correct 36 ms 15236 KB Output is correct
8 Correct 50 ms 15936 KB Output is correct
9 Correct 43 ms 15908 KB Output is correct

Subtask #2
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 15408 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 30 ms 14792 KB Output is correct
4 Correct 43 ms 16480 KB Output is correct
5 Correct 43 ms 16572 KB Output is correct
6 Correct 37 ms 15196 KB Output is correct
7 Correct 36 ms 15236 KB Output is correct
8 Correct 50 ms 15936 KB Output is correct
9 Correct 43 ms 15908 KB Output is correct
10 Correct 31 ms 13484 KB Output is correct
11 Execution timed out 3097 ms 13360 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 13032 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 29 ms 12616 KB Output is correct
4 Correct 44 ms 14172 KB Output is correct
5 Correct 40 ms 14312 KB Output is correct
6 Correct 37 ms 12936 KB Output is correct
7 Correct 37 ms 13008 KB Output is correct
8 Correct 55 ms 13604 KB Output is correct
9 Correct 41 ms 13652 KB Output is correct
10 Correct 35 ms 13352 KB Output is correct
11 Correct 39 ms 13388 KB Output is correct
12 Correct 36 ms 13400 KB Output is correct
13 Correct 38 ms 13476 KB Output is correct
14 Correct 52 ms 13676 KB Output is correct
15 Correct 43 ms 13676 KB Output is correct

Subtask #4
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 13032 KB Output is correct
2 Correct 1 ms 1024 KB Output is correct
3 Correct 29 ms 12616 KB Output is correct
4 Correct 44 ms 14172 KB Output is correct
5 Correct 40 ms 14312 KB Output is correct
6 Correct 37 ms 12936 KB Output is correct
7 Correct 37 ms 13008 KB Output is correct
8 Correct 55 ms 13604 KB Output is correct
9 Correct 41 ms 13652 KB Output is correct
10 Correct 35 ms 13352 KB Output is correct
11 Correct 39 ms 13388 KB Output is correct
12 Correct 36 ms 13400 KB Output is correct
13 Correct 38 ms 13476 KB Output is correct
14 Correct 52 ms 13676 KB Output is correct
15 Correct 43 ms 13676 KB Output is correct
16 Correct 28 ms 11600 KB Output is correct
17 Execution timed out 3085 ms 11536 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1284 KB Output is correct
2 Correct 1 ms 1032 KB Output is correct
3 Correct 2 ms 1288 KB Output is correct
4 Incorrect 2 ms 1296 KB Wrong Answer [5]
5 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

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

Subtask #7
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 31 ms 11304 KB Output is correct
2 Correct 37 ms 12356 KB Output is correct
3 Incorrect 1 ms 1108 KB Wrong Answer [5]
4 Halted 0 ms 0 KB -