oj.uz

Submission #373102

# Submission time Handle Problem Language Result Execution time Memory
373102 2021-03-03T10:57:39 Z Vladth11 Travelling Salesperson (CCO20_day2problem1) C++14
0 / 25
 742 ms 24428 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;
            if(dq.back().second == 2)
                ok = 0;
            dq.pop_back();
            if(!ok){
                dq.back().second = 2;
            }
            dq.push_front({dr, 0});
            insert(i);
            return;
        }else{
            int ok = 1;
            if(dq.front().second == 2)
                ok = 0;
            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:85:12: warning: unused variable 'i' [-Wunused-variable]
   85 |     int n, i, j;
      |            ^
Main.cpp:85:15: warning: unused variable 'j' [-Wunused-variable]
   85 |     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 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 376 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 384 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 699 ms 24172 KB Output is correct
17 Correct 687 ms 24300 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 699 ms 24044 KB Output is correct
20 Correct 737 ms 24168 KB Output is correct
21 Correct 1 ms 492 KB Output is correct
22 Correct 674 ms 24044 KB Output is correct
23 Correct 704 ms 23916 KB Output is correct
24 Correct 2 ms 620 KB Output is correct
25 Correct 687 ms 24036 KB Output is correct
26 Correct 695 ms 24200 KB Output is correct
27 Correct 42 ms 2540 KB Output is correct
28 Correct 681 ms 24300 KB Output is correct
29 Correct 685 ms 24112 KB Output is correct
30 Correct 688 ms 24224 KB Output is correct
31 Correct 687 ms 24044 KB Output is correct
32 Correct 676 ms 23916 KB Output is correct
33 Correct 686 ms 24172 KB Output is correct
34 Correct 662 ms 23948 KB Output is correct
35 Correct 686 ms 24108 KB Output is correct
36 Correct 672 ms 24428 KB Output is correct
37 Correct 675 ms 23916 KB Output is correct
38 Correct 698 ms 24148 KB Output is correct
39 Correct 731 ms 24044 KB Output is correct
40 Correct 701 ms 24172 KB Output is correct
41 Correct 715 ms 24044 KB Output is correct
42 Correct 680 ms 24124 KB Output is correct
43 Correct 686 ms 24172 KB Output is correct
44 Correct 660 ms 24044 KB Output is correct
45 Correct 674 ms 24300 KB Output is correct
46 Correct 688 ms 24036 KB Output is correct
47 Correct 700 ms 24320 KB Output is correct
48 Correct 704 ms 24172 KB Output is correct
49 Correct 690 ms 24172 KB Output is correct
50 Correct 690 ms 24040 KB Output is correct
51 Correct 685 ms 23916 KB Output is correct
52 Correct 723 ms 24172 KB Output is correct
53 Correct 687 ms 24064 KB Output is correct
54 Correct 671 ms 24300 KB Output is correct
55 Correct 742 ms 24172 KB Output is correct
56 Incorrect 735 ms 24200 KB Output isn't correct
57 Halted 0 ms 0 KB -