Submission #970621

#	Time	Username	Problem	Language	Result	Execution time	Memory
970621		Art_ogo	Dango Maker (JOI18_dango_maker)	C++17	0 / 100	41 ms	96216 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
#define ve vector
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC optimize("avx2")

typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e3+10;

set<int> g[2*MAXN*MAXN];
int n, m;

int toid(int i, int j){
    return i*m + j;
}

void add(int i1, int j1, int dir1, int i2, int j2, int dir2){ // 0 - hor, 1 - ver
    int a = 2*toid(i1, j1) + dir1;
    int b = 2*toid(i2, j2) + dir2;
    g[a].insert(b);
    g[b].insert(a);
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    ve<string> v(n);
    for(auto& i : v)
        cin >> i;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(v[i][j] == 'R'){
                bool ok1 = i + 2 < n && v[i + 1][j] == 'G' && v[i + 2][j] == 'W';
                bool ok2 = j + 2 < m && v[i][j + 1] == 'G' && v[i][j + 2] == 'W';
                if(ok1 && ok2)
                    add(i, j, 0, i, j, 1);
            }
            else if(v[i][j] == 'G'){
                bool ok1 = i - 1 >= 0 && i + 1 < n && v[i - 1][j] == 'R' && v[i + 1][j] == 'W';
                bool ok2 = j - 1 >= 0 && j + 1 < m && v[i][j - 1] == 'R' && v[i][j + 1] == 'W';
                if(ok1 && ok2)
                    add(i - 1, j, 0, i, j - 1, 1);
            }
            else if(v[i][j] == 'W'){
                bool ok1 = i - 2 >= 0 && v[i - 2][j] == 'R' && v[i - 1][j] == 'G';
                bool ok2 = j - 2 >= 0 && v[i][j - 2] == 'R' && v[i][j - 1] == 'G';
                if(ok1 && ok2)
                    add(i - 2, j, 0, i, j - 2, 1);
            }
        }
    }
    int res = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++){
            if(g[toid(i, j)*2].empty() && i + 2 < n && v[i][j] == 'R' && v[i + 1][j] == 'G' && v[i + 2][j] == 'W')
                res++;
            if(g[toid(i, j)*2 + 1].empty() && j + 2 < m && v[i][j] == 'R' && v[i][j + 1] == 'G' && v[i][j + 2] == 'W')
                res++;
        }
    queue<int> q;
    for(int i = 0; i < 2*n*m; i++)
        if(g[i].size() == 1)
            q.push(i);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        if(g[v].empty())
            continue;
        res++;
        int to = *g[v].begin();
        g[v].erase(to);
        g[to].erase(v);
        if(g[to].size() == 1)
            q.push(to);
    }
    for(int i = 0; i < 2*n*m; i++)
        if(g[i].size())
            res++;
    cout << res;
}

Compilation message (stderr)

dango_maker.cpp:12:28: warning: bad option '-favx2' to pragma 'optimize' [-Wpragmas]
   12 | #pragma GCC optimize("avx2")
      |                            ^
dango_maker.cpp:22:22: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   22 | int toid(int i, int j){
      |                      ^
dango_maker.cpp:26:60: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   26 | void add(int i1, int j1, int dir1, int i2, int j2, int dir2){ // 0 - hor, 1 - ver
      |                                                            ^
dango_maker.cpp:33:13: warning: bad option '-favx2' to attribute 'optimize' [-Wattributes]
   33 | signed main() {
      |             ^

• Subtask 1: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67