제출 #786962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
786962		JoenPoenMan	길고양이 (JOI20_stray)	C++17	15 / 100	56 ms	19084 KiB

Anthony

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

typedef pair<int, int> ii;

std::vector<int> Mark(int N, int M, int A, int B,
                      std::vector<int> U, std::vector<int> V)
{


    vector<vector<ii>> ADJ(N);
    map<ii, int> paths;
    vector<bool> filled(M, false);

    for (int i = 0; i < M; i++) {
        ADJ[U[i]].push_back({V[i], i});
        ADJ[V[i]].push_back({U[i], i});
        paths[{U[i], V[i]}] = i;
        paths[{V[i], U[i]}] = i;
    }

    std::vector<int> X(M);
    if (A == 2) {
        vector<optional<bool>> marker(N);
        vector<int> prev (N, -1);
        int straightlength = 0;
        bool pattern[6] = {true, false, true, true, false, false};
        stack<int> s;
        s.push(0);
        marker[0] = false;
        while (!s.empty()) {
            int pos = s.top();
            s.pop();
            for (auto [other, ind] : ADJ[pos]) {
                if (!marker[other]) {
                    s.push(other);
                    prev[other] = pos;
                    if (ADJ[pos].size() <= 2) {
                        marker[other] = pattern[straightlength%6];

                        straightlength++;
                    } else {
                        straightlength = 0;
                        marker[other] = !(*marker[pos]);
                    }
                }

            }
        }

        for (int i = 1; i < N; i++) {
            X[paths[{i, prev[i]}]] = (*marker[i]);
        }
        return X;
    }

    priority_queue<ii, vector<ii>, greater<ii>> q;
    vector<int> prevNode(N, -1);
    vector<int> shortest(N, 1e8);
    shortest[0] = 0;
    q.push({0,0});
    while (!q.empty()) {
        auto [dis, pos] = q.top();
        q.pop();
        if (dis != shortest[pos]) continue;
        for (auto [conn, _] : ADJ[pos]) {
            if (dis+1 < shortest[conn]) {
                shortest[conn] = dis+1;
                prevNode[conn] = pos;
                q.push({dis+1, conn});
            }
        }
    }

    

    for (int p = 1; p < N; p++) {
        X[paths[{p, prevNode[p]}]] = shortest[p]%(A==2?2:3);
        filled[paths[{p, prevNode[p]}]] = true;
    }
    for (int i = 0; i < M; i++) if (!filled[i]) {
        X[i] = (min(shortest[U[i]], shortest[V[i]])+1)%(A==2?2:3);
    }
    return X;
    
}

Catherine

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

namespace
{

    int A, B;
    int prevA = 0;
    bool onPath = false;
    bool first = true;
    bool code[5];
    int codeCount = 2;

    int findNext2(vector<int> y) {
        if (!::onPath) {
            if (::first) {
                ::first = false;
                if (y[0]+y[1] != 2) {
                    ::onPath = true;
                    return (y[0] == 1 ? 0 : 1);
                }
                if (y[0] == 2) {
                    code[0] = false, code[1] = false;
                    return 0;
                }
                if (y[1] == 2) code[0] = false, code[1] = false;
                else code[0] = false, code[1] = true;
                return 1;
            }
            if (y[0] + y[1] > 1) {
                ::onPath = true;
                return (y[0] == 1 && prevA != 0 ? 0 : (y[1] == 1 && prevA != 1 ? 1 : -1));
            } else if (y[0] + y[1] == 0) {
                ::onPath = true;
                return -1;
            } else {
                code[codeCount] = (y[0] ? 0 : 1);
                codeCount++;
                if (codeCount == 5) {
                    onPath = true;
                    return (code[4] == 0 ? -1 : 1);
                }
                if (codeCount == 4) {
                    ::onPath = true;
                    if (code[0] == 0 && code[1] == 0) {
                        if (code[3] == 0) return -1;
                        else return 1;
                    }
                    if (code[0] && code[1]) {
                        if (code[3] == 0) return -1;
                        else return 1;
                    }
                    if (code[2] == 0) {
                        if (code[3] == 1) return -1;
                        else return 0;
                    }
                    onPath = false;
                }
                return (y[0] ? 0 : 1);
            }
        } else {
            return (y[0] ? 0 : 1);
        }
    }

} 

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

int Move(std::vector<int> y)
{
    if (A==2) {
        int res = ::findNext2(y);
        if (res != -1) ::prevA = res;
        return res;
    } else {
        first = false;
        int corr = -1;
        for (int p = 0 ; p < y.size(); p++) if (y[p] && (corr==-1 || (corr==0&&p==2))) corr = p;
        return corr;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:86:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int p = 0 ; p < y.size(); p++) if (y[p] && (corr==-1 || (corr==0&&p==2))) corr = p;
      |                          ~~^~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 2 / 2
• Subtask 3: 2 / 2
• Subtask 4: 9 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 71
• Subtask 7: 0 / 9