oj.uz

Submission #373104

# Submission time Handle Problem Language Result Execution time Memory
373104 2021-03-03T10:59:00 Z Vladth11 Travelling Salesperson (CCO20_day2problem1) C++14
0 / 25
 773 ms 23804 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.back().second == 0 || dq.back().second == 2)){
            dq.push_back({i, 0});
            return;
        }
        if(mat[st][dr] == 'R'){
            int ok = 1;
            dq.pop_back();
            if(!ok){
                dq.back().second = 2;
            }
            dq.push_front({dr, 0});
            insert(i);
            return;
        }else{
            int ok = 1;
            dq.pop_front();
             if(!ok){
                dq.front().second = 2;
            }
            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:81:12: warning: unused variable 'i' [-Wunused-variable]
   81 |     int n, i, j;
      |            ^
Main.cpp:81:15: warning: unused variable 'j' [-Wunused-variable]
   81 |     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 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 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 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 717 ms 23532 KB Output is correct
17 Correct 704 ms 23804 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 773 ms 23516 KB Output is correct
20 Correct 731 ms 23660 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 721 ms 23532 KB Output is correct
23 Correct 738 ms 23424 KB Output is correct
24 Correct 2 ms 620 KB Output is correct
25 Correct 678 ms 23532 KB Output is correct
26 Correct 705 ms 23560 KB Output is correct
27 Correct 43 ms 2412 KB Output is correct
28 Correct 697 ms 22892 KB Output is correct
29 Correct 696 ms 22892 KB Output is correct
30 Correct 704 ms 22892 KB Output is correct
31 Correct 679 ms 22764 KB Output is correct
32 Correct 668 ms 22892 KB Output is correct
33 Correct 681 ms 22936 KB Output is correct
34 Correct 685 ms 22892 KB Output is correct
35 Correct 685 ms 23076 KB Output is correct
36 Correct 696 ms 23020 KB Output is correct
37 Correct 680 ms 22892 KB Output is correct
38 Correct 681 ms 22940 KB Output is correct
39 Correct 683 ms 22772 KB Output is correct
40 Correct 692 ms 22776 KB Output is correct
41 Correct 683 ms 22424 KB Output is correct
42 Correct 698 ms 22252 KB Output is correct
43 Correct 681 ms 22520 KB Output is correct
44 Correct 676 ms 22580 KB Output is correct
45 Correct 687 ms 22380 KB Output is correct
46 Correct 680 ms 22252 KB Output is correct
47 Correct 710 ms 22380 KB Output is correct
48 Correct 680 ms 22380 KB Output is correct
49 Correct 676 ms 22380 KB Output is correct
50 Correct 680 ms 22380 KB Output is correct
51 Correct 683 ms 22252 KB Output is correct
52 Correct 710 ms 22380 KB Output is correct
53 Correct 676 ms 22380 KB Output is correct
54 Correct 683 ms 22508 KB Output is correct
55 Correct 721 ms 22380 KB Output is correct
56 Incorrect 733 ms 22508 KB Output isn't correct
57 Halted 0 ms 0 KB -