Submission #373105

#	Time	Username	Problem	Language	Result	Execution time	Memory
373105		Vladth11	Travelling Salesperson (CCO20_day2problem1)	C++14	25 / 25	845 ms	24428 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "
//#include "shoes.h"

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <ll, pii> piii;
typedef tree <pii, null_type, less <pii>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 2001;
const ll INF = (1LL << 31);
const ll MOD = 1000000007;
const ll BLOCK = 316;
const ll nr_of_bits = 20;
const double eps = 0.0000000001;

char mat[NMAX][NMAX];

struct muchie{
    int first, cul, second;
};

class lant{
public:
    deque <muchie> dq;
    int primul;
    void init(){
        primul = -1;
        while(dq.size())
            dq.pop_back();
    }
    void insert(int i){
        if(dq.size() == 0 && primul == -1){
            primul = i;
            return;
        }else if(dq.size() == 0){
            if(mat[i][primul] == 'R')
            dq.push_front({i, 0, primul});
            else dq.push_back({primul, 1, i});
            return;
        }
        int st = dq.front().first;
        int dr = dq.back().second;
        ///putem alipi la stanga sau dreapta
        if(mat[st][i] == 'R'){
            dq.push_front({i, 0, st});
            return;
        }else if(mat[st][i] == 'B' && (dq.front().cul == 1)){
            dq.push_front({i, 1, st});
            return;
        }else if(mat[dr][i] == 'B'){
            dq.push_back({dr, 1, i});
            return;
        }else if(mat[dr][i] == 'R' && (dq.back().cul == 0)){
            dq.push_back({dr, 0, i});
            return;
        }
        if(mat[st][dr] == 'R'){
            dq.pop_back();
            dq.push_front({dr, 0, st});
            insert(i);
            return;
        }else{
            dq.pop_front();
            dq.push_back({dr, 1, st});
            insert(i);
            return;
        }
    }
}l;

int main() {
    int n, i, j;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            cin >> mat[i][j];
            mat[j][i] = mat[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        l.init();
        for(int j = 1; j <= n; j++){
            if(i == j)
                continue;
            l.insert(j);
        }
        l.insert(i);
        cout << n << "\n";
        if(l.dq.front().first == i){
            for(auto x : l.dq){
                cout << x.first << " ";
            }
            cout << l.dq.back().second << " ";
        }else{
            while(l.dq.size()){
                cout << l.dq.back().second << " ";
                if(l.dq.size() == 1){
                    cout << l.dq.back().first << " ";
                }
                l.dq.pop_back();
            }
        }
        cout << "\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:78:12: warning: unused variable 'i' [-Wunused-variable]
   78 |     int n, i, j;
      |            ^
Main.cpp:78:15: warning: unused variable 'j' [-Wunused-variable]
   78 |     int n, i, j;
      |               ^

• Subtask 1: 25 / 25