Submission #375995

#	Time	Username	Problem	Language	Result	Execution time	Memory
375995		mihai145	Travelling Salesperson (CCO20_day2problem1)	C++14	25 / 25	490 ms	22636 KiB

Main

#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

const int NMAX = 2000;

int N;
string m[NMAX + 2];

///0-> BLUE
///1-> RED
bool Edge(int x, int y) {
    if(x < y) {
        swap(x, y);
    }

    if(m[x][y] == 'B') {
        return 0;
    }

    return 1;
}

deque <int> dq;
void Push(int vert) {
    if(dq.empty()) {
        dq.push_back(vert);
    } else {
        if(Edge(dq.back(), vert) == 1) {
            dq.push_back(vert);
        } else if(Edge(dq.front(), vert) == 0) {
            dq.push_front(vert);
        } else if(Edge(dq.front(), dq.back()) == 1) {
            int frontVert = dq.front();
            dq.pop_front();
            dq.push_back(frontVert);
            dq.push_back(vert);
        } else {
            int backVert = dq.back();
            dq.pop_back();
            dq.push_front(backVert);
            dq.push_front(vert);
        }
    }
}

void SolveFor(int vert) {
    dq.clear();

    for(int i = 0; i < N; i++) {
        if(i != vert) {
            Push(i);
        }
    }

    Push(vert);

    if(dq.back() == vert) {
        reverse(dq.begin(), dq.end());
    }

    cout << N << '\n';
    for(int v : dq) {
        cout << v + 1 << ' ';
    }
    cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;

    for(int i = 1; i < N; i++) {
        cin >> m[i];
    }

    for(int i = 0; i < N; i++) {
        SolveFor(i);
    }

    return 0;
}

• Subtask 1: 25 / 25