Submission #372980

# Submission time Handle Problem Language Result Execution time Memory
372980 2021-03-02T21:23:33 Z Vladth11 Travelling Salesperson (CCO20_day2problem1) C++14
0 / 25
1 ms 364 KB
#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];

class lant{
public:
    deque <pii> dq;
    void init(){
        while(dq.size())
            dq.pop_back();
    }
    void insert(int i){
        if(dq.size() == 0){
            dq.push_back({i, 2});
            return;
        }else if(dq.size() == 1){
            int st =dq.front().first;
            if(mat[i][st] == 'R')
            dq.push_front({i, 0});
            else dq.push_back({i, 1});
            return;
        }
        int st = dq.front().first;
        int dr = dq.back().first;
        ///putem alipi la stanga sau dreapta
        if(mat[st][i] == 'R'){
            dq.push_front({i, 0});
            return;
        }else if(mat[st][i] == 'B' && (dq.front().second == 1 || dq.front().second == 2)){
            dq.push_front({i, 1});
            return;
        }else if(mat[dr][i] == 'B'){
            dq.push_back({i, 1});
            return;
        }else if(mat[dr][i] == 'R' && (dq.front().second == 0 || dq.front().second == 2)){
            dq.push_front({i, 0});
            return;
        }
        if(mat[st][dr] == 'R'){
            dq.pop_back();
            dq.push_front({dr, 0});
            insert(i);
            return;
        }else{
            dq.pop_front();
            dq.push_back({st, 1});
            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 << " ";
            }
        }else{
            while(l.dq.size()){
                cout << l.dq.back().first << " ";
                l.dq.pop_back();
            }
        }
        cout << "\n";
    }
    return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:73:12: warning: unused variable 'i' [-Wunused-variable]
   73 |     int n, i, j;
      |            ^
Main.cpp:73:15: warning: unused variable 'j' [-Wunused-variable]
   73 |     int n, i, j;
      |               ^
# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Incorrect 1 ms 364 KB Output isn't correct
9 Halted 0 ms 0 KB -