oj.uz

Submission #970621

# Submission time Handle Problem Language Result Execution time Memory
970621 2024-04-26T20:23:29 Z Art_ogo Dango Maker (JOI18_dango_maker) C++17
0 / 100
 41 ms 96216 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 96084 KB Output is correct
2 Correct 22 ms 96092 KB Output is correct
3 Correct 20 ms 96092 KB Output is correct
4 Correct 20 ms 96092 KB Output is correct
5 Correct 21 ms 96092 KB Output is correct
6 Incorrect 20 ms 96216 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 96084 KB Output is correct
2 Correct 22 ms 96092 KB Output is correct
3 Correct 20 ms 96092 KB Output is correct
4 Correct 20 ms 96092 KB Output is correct
5 Correct 21 ms 96092 KB Output is correct
6 Incorrect 20 ms 96216 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 96084 KB Output is correct
2 Correct 22 ms 96092 KB Output is correct
3 Correct 20 ms 96092 KB Output is correct
4 Correct 20 ms 96092 KB Output is correct
5 Correct 21 ms 96092 KB Output is correct
6 Incorrect 20 ms 96216 KB Output isn't correct
7 Halted 0 ms 0 KB -