Untitled

 avatar
user_0483151
plain_text
9 months ago
3.4 kB
10
Indexable
// kjhlaskfdj
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define bit(x, i) ( ( x >> i ) & 1 )
#define mask(i) ( (1LL) << (i) )
#define cook '\n'
#define Task "chocolate"

using namespace std ;

const int dx[] = {0, 1, 0, -1} ;
const int dy[] = {1, 0, -1, 0} ;
const int mod = 1e9 + 7 ;
const int maxn = 1e6 + 5 ;

struct Edge {
    int x, y, dir ;
    Edge(int _x = 0, int _y = 0, int _dir = 0) {
        x = _x; y = _y; dir = _dir ;
    }
    bool operator < ( const Edge & other ) const {
        if ( x != other.x ) return x < other.x ;
        if ( y != other.y ) return y < other.y ;
        return dir < other.dir ;
    }
    bool operator == ( const Edge & other ) const {
        return ( x == other.x && y == other.y && dir == other.dir ) ;
    }
};

int numRow, numCol, numEdge ;

set<Edge> saveEdge ;

int get(char c) {
    if ( c == 'R' ) return 0 ;
    if ( c == 'U' ) return 1 ;
    if ( c == 'L' ) return 2 ;
    if ( c == 'D' ) return 3 ;
}

bool check(int x, int y, int dir) { // RULD
    if ( ( x == 0 || x == numRow) && (dir % 2 == 0) ) return true ;
    if ( ( y == 0 || y == numCol) && (dir % 2 == 1) ) return true ;
    return false ;
}

void inp() {
    int x, y ;
    cin >> numCol >> numRow >> numEdge >> y >> x ;
    for ( int i = 1; i <= numEdge; i++ ) {
        char c; cin >> c ;
        int dir = get(c), rev = ( dir + 2 ) % 4 ;
        if ( check(x, y, dir) == false && saveEdge.find(Edge(x, y, dir)) == saveEdge.end() )
            saveEdge.insert(Edge(x, y, dir)) ;
        x += dx[dir] ; y += dy[dir] ;
        if ( check(x, y, rev) == false && saveEdge.find(Edge(x, y, rev)) == saveEdge.end() )
            saveEdge.insert(Edge(x, y, rev)) ;
    }
    for ( int i = 0; i <= numCol; i++ ) {
        if ( i < numCol ) saveEdge.insert(Edge(0, i, 0)) ;
        if ( i > 0 ) saveEdge.insert(Edge(numRow, i, 2)) ;
    }
    for ( int i = 0; i <= numRow; i++ ) {
        if ( i > 0 ) saveEdge.insert(Edge(i, 0, 3)) ;
        if ( i < numRow ) saveEdge.insert(Edge(i, numCol, 1)) ;
    }

//    for ( auto &e : saveEdge ) cout << e.x << ' ' << e.y << ' ' << e.dir << cook ;
}

vector<long long> S ;

void solve(Edge e) {
    long long re = 0, H = 1e5 ;
    int x = e.x, y = e.y, dir = e.dir;
    x += dx[dir]; y += dy[dir] ;

    int dem = 0;
    while ( true ) {
        for ( int i = 5; i >= 2; i-- ) {
            if ( saveEdge.find(Edge(x, y, (dir + i) % 4)) != saveEdge.end() ) {
                dir = ( dir + i ) % 4 ;
                saveEdge.erase(Edge(x, y, dir)) ;
                break ;
            }
        }

        if ( dir == 0 ) re -= H ;
        else if ( dir == 1 ) H++ ;
        else if ( dir == 2 ) re += H ;
        else if ( dir == 3 ) H-- ;

        if ( x == e.x && y == e.y && dir == e.dir ) break ;

        x += dx[dir]; y += dy[dir] ;
    }

    S.push_back(re) ;
}

signed main() {
    ios_base::sync_with_stdio(0) ;
    cin.tie(nullptr) ;
    if ( fopen(Task".inp", "r") ) {
        freopen(Task".inp", "r", stdin) ;
        freopen(Task".out", "w", stdout) ;
    }
    inp() ;
    while ( !saveEdge.empty() ){
        auto e = *saveEdge.begin() ;
        solve(e) ;
    }
    sort(all(S)) ; cout << S.size() << cook ;
    for ( const long long &s : S ) cout << s << ' ' ;
}
Editor is loading...
Leave a Comment