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

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];

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;
      |               ^

Subtask #1

0 / 25.0

#	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	-