oj.uz

Submission #939149

# Submission time Handle Problem Language Result Execution time Memory
939149 2024-03-06T06:16:18 Z vjudge1 Dango Maker (JOI18_dango_maker) C++17
13 / 100
 109 ms 255920 KB 
#include <bits/stdc++.h>  
using namespace std;
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast") 
//#pragma comment(linker, "/stack:200000000") 
#pragma GCC target( "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native" ) 
#pragma GCC optimize("unroll-loops")
/* 
#pragma GCC optimize("profile-values,profile-reorder-functions,tracer") 
#pragma GCC optimize("vpt") 
#pragma GCC optimize("rename-registers") 
#pragma GCC optimize("move-loop-invariants") 
#pragma GCC optimize("unswitch-loops") 
#pragma GCC optimize("function-sections") 
#pragma GCC optimize("data-sections") 
#pragma GCC optimize("branch-target-load-optimize") 
#pragma GCC optimize("branch-target-load-optimize2") 
#pragma GCC optimize("btr-bb-exclusive") 
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse") 
#pragma GCC optimize("-fgcse-lm") 
#pragma GCC optimize("-fipa-sra") 
#pragma GCC optimize("-ftree-pre") 
#pragma GCC optimize("-ftree-vrp") 
#pragma GCC optimize("-fpeephole2") 
#pragma GCC optimize("-ffast-math") 
#pragma GCC optimize("-fsched-spec") 
#pragma GCC optimize("-falign-jumps") 
#pragma GCC optimize("-falign-loops") 
#pragma GCC optimize("-falign-labels") 
#pragma GCC optimize("-fdevirtualize") 
#pragma GCC optimize("-fcaller-saves") 
#pragma GCC optimize("-fcrossjumping") 
#pragma GCC optimize("-fthread-jumps") 
#pragma GCC optimize("-freorder-blocks") 
#pragma GCC optimize("-fschedule-insns") 
#pragma GCC optimize("inline-functions") 
#pragma GCC optimize("-ftree-tail-merge") 
#pragma GCC optimize("-fschedule-insns2") 
#pragma GCC optimize("-fstrict-aliasing") 
#pragma GCC optimize("-falign-functions") 
#pragma GCC optimize("-fcse-follow-jumps") 
#pragma GCC optimize("-fsched-interblock") 
#pragma GCC optimize("-fpartial-inlining") 
#pragma GCC optimize("no-stack-protector") 
#pragma GCC optimize("-freorder-functions") 
#pragma GCC optimize("-findirect-inlining") 
#pragma GCC optimize("-fhoist-adjacent-loads") 
#pragma GCC optimize("-frerun-cse-after-loop") 
#pragma GCC optimize("inline-small-functions") 
#pragma GCC optimize("-finline-small-functions") 
#pragma GCC optimize("-ftree-switch-conversion") 
#pragma GCC optimize("-foptimize-sibling-calls") 
#pragma GCC optimize("-fexpensive-optimizations") 
#pragma GCC optimize("inline-functions-called-once") 
#pragma GCC optimize("-fdelete-null-pointer-checks")
*/
#define ll long long 
#define all(x) x.begin(),x.end()
#define sz(x) (int) x.size()
#define f first
#define s second
#define ld long double
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define pb push_back
#define dauzhan gay
#define popcount __builtin_popcount
const long double Eps = 1e-12; 
const int max1 = 1e9 + 100; 
const int min1 = -1e9 *1.4;
const ll mod1 = 1000000007;
const ll mod2 = 2000000011;
const ll mod3 = 3000000017;
const ll mod = 998244353;
const int N = 2e5 + 100;
const int B = 9000000 + 1;
const ll INF = 1e18 + 100;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll binpow(ll x,ll y,ll md) {
    if(y < 0) return 0;
    if(y == 0) return 1;        
    if(y == 1) return x;
    if(y % 2 == 0) {
        ll now = binpow(x,y/2,md);
        return (1ll*now*now) % md;
    }
    else {
        ll now = binpow(x,y/2,md);
        return (1ll*((1ll*now*now) % md)*x) % md;
    }
}
/*
for(int i = 1;i <= n;i++) sp[0][i] = a[i];
for(int i = 1;i <= log2(n);i++) {
    for(int l = 1;l <= n;l++) {
        int r = l + (1 << i) - 1;
        if(r > n) break;
        int middle = l + (1 << (i - 1));
        sp[i][l] = max(sp[i - 1][l],sp[i - 1][middle]);
    }
}
int get(int l,int r) {
    int g = log2(r - l + 1);
    return max(sp[g][l],sp[g][r - (1 << g) + 1]);
} 
*/
int matching[B];
bool used[B];
vector <int> reb[B];
bool dfs(int v) {
    if(used[v]) return false;
    used[v] = true;
    for(auto to:reb[v]) {
        if(matching[to] == -1 || dfs(matching[to])) {
            matching[to] = v;
            return true;
        }
    }
    return false;
}
int n,m;

int f(int x,int y) {
    return (x - 1)*m + y;
}
pair <int,int> g(int x) {
    int b = x % m;
    if(b == 0) b = m;
    return {(x - b)/m + 1,b};
}
signed main() {
    ios_base::sync_with_stdio(NULL);
    cin.tie(0);
    cout.tie(0);    
    cin >> n >> m;
    char a[n + 1][m + 1];
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            cin >> a[i][j];
        }
    }
    //a[i][j] = (i - 1)*m + j;
    memset(matching,-1,sizeof(matching));
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            if(a[i][j] == 'G') {
                if((i < n&&a[i + 1][j] == 'W') || (j < m&&a[i][j + 1] == 'W')) {
                    if(i > 1&&a[i - 1][j] == 'R') {
                        int x = f(i - 1,j);
                        int y = f(i,j);
                        reb[x].pb(y);
                        reb[y].pb(x);
                    }
                    if(j > 1&&a[i][j - 1] == 'R') {
                        int x = f(i,j - 1);
                        int y = f(i,j);
                        reb[x].pb(y);
                        reb[y].pb(x);
                    }
                }
            }
        }
    }
    for(int i = 1;i <= n*m;i++) {
        memset(used,false,sizeof(used));
        dfs(i);
    }
    bool chose[n + 1][m + 1];
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            chose[i][j] = false;
        }
    }
    for(int i = 1;i <= n*m;i++) {
        if(matching[i] != -1) {
            int x = i,y = matching[i];
            int x1 = g(x).f,y1 = g(x).s;
            int x2 = g(y).f,y2 = g(y).s;
            if(x1 > n || x1 < 1 || y1 > m || y1 < 1 || x2 > n || x2 < 1) {
                cout << 1/0 << endl;
                exit(0);
            }
            if(a[x1][y1] == 'G') {
                chose[x1][y1] = true;
            }
            if(a[x2][y2] == 'G') {
                chose[x2][y2] = true;
            }
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= m;j++) {
            if(a[i][j] == 'W') {
                if(j > 1&&chose[i][j - 1]) {
                    chose[i][j - 1] = false;
                    ans++;
                }
                else if(i > 1&&chose[i - 1][j]) {
                    chose[i - 1][j] = false;
                    ans++;
                }
            }
        }
    }
    cout << ans << endl;
}

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:181:26: warning: division by zero [-Wdiv-by-zero]
  181 |                 cout << 1/0 << endl;
      |                         ~^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 255792 KB Output is correct
2 Correct 96 ms 255784 KB Output is correct
3 Correct 109 ms 255920 KB Output is correct
4 Correct 95 ms 255572 KB Output is correct
5 Correct 101 ms 255572 KB Output is correct
6 Correct 96 ms 255644 KB Output is correct
7 Correct 98 ms 255816 KB Output is correct
8 Correct 96 ms 255572 KB Output is correct
9 Correct 95 ms 255572 KB Output is correct
10 Correct 95 ms 255568 KB Output is correct
11 Correct 97 ms 255572 KB Output is correct
12 Correct 102 ms 255572 KB Output is correct
13 Correct 98 ms 255568 KB Output is correct
14 Correct 105 ms 255812 KB Output is correct
15 Correct 97 ms 255564 KB Output is correct
16 Correct 99 ms 255604 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 255792 KB Output is correct
2 Correct 96 ms 255784 KB Output is correct
3 Correct 109 ms 255920 KB Output is correct
4 Correct 95 ms 255572 KB Output is correct
5 Correct 101 ms 255572 KB Output is correct
6 Correct 96 ms 255644 KB Output is correct
7 Correct 98 ms 255816 KB Output is correct
8 Correct 96 ms 255572 KB Output is correct
9 Correct 95 ms 255572 KB Output is correct
10 Correct 95 ms 255568 KB Output is correct
11 Correct 97 ms 255572 KB Output is correct
12 Correct 102 ms 255572 KB Output is correct
13 Correct 98 ms 255568 KB Output is correct
14 Correct 105 ms 255812 KB Output is correct
15 Correct 97 ms 255564 KB Output is correct
16 Correct 99 ms 255604 KB Output is correct
17 Correct 99 ms 255572 KB Output is correct
18 Correct 101 ms 255668 KB Output is correct
19 Incorrect 105 ms 255568 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 255792 KB Output is correct
2 Correct 96 ms 255784 KB Output is correct
3 Correct 109 ms 255920 KB Output is correct
4 Correct 95 ms 255572 KB Output is correct
5 Correct 101 ms 255572 KB Output is correct
6 Correct 96 ms 255644 KB Output is correct
7 Correct 98 ms 255816 KB Output is correct
8 Correct 96 ms 255572 KB Output is correct
9 Correct 95 ms 255572 KB Output is correct
10 Correct 95 ms 255568 KB Output is correct
11 Correct 97 ms 255572 KB Output is correct
12 Correct 102 ms 255572 KB Output is correct
13 Correct 98 ms 255568 KB Output is correct
14 Correct 105 ms 255812 KB Output is correct
15 Correct 97 ms 255564 KB Output is correct
16 Correct 99 ms 255604 KB Output is correct
17 Correct 99 ms 255572 KB Output is correct
18 Correct 101 ms 255668 KB Output is correct
19 Incorrect 105 ms 255568 KB Output isn't correct
20 Halted 0 ms 0 KB -