Submission #1050266

#TimeUsernameProblemLanguageResultExecution timeMemory
1050266vjudge1Dango Maker (JOI18_dango_maker)C++17
13 / 100
19 ms36040 KiB
#include<bits/stdc++.h>
#define en "\n"
#define s second
#define f first
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define vi vector<int>
#define vii vector<pair<int,int>>
// #define int long long
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define loop(a) for(int i = 0; i < a; i++)
#define loopv(i,a) for (int i = 0; i < a; i++)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) printf("%.8f", x)
#define goog(tno) printf("Case #%d: ", tno)
using namespace std;
const int N = 3010;
int n, m;
vector <vi> a(N, vi(N, 3));
map<pair<int, int>, int> mp;

void solve() {
    cin>>n>>m;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            cin>>c;
            if(c=='R'){
                a[i][j]=0;
            }
            else if(c=='G'){
                a[i][j]=1;
            }
            else{
                a[i][j]=2;
            }
        }
    }
    
    // Horizontal checks
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m-2; j++){
            if(a[i][j]==0 and a[i][j+1]==1 and a[i][j+2]==2){
                mp[{i,j}]++;
                mp[{i,j+1}]++;
                mp[{i,j+2}]++;
            }
        }
    }
    
    // Vertical checks
    for(int i=1; i<=n-2; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j]==0 and a[i+1][j]==1 and a[i+2][j]==2){
                mp[{i,j}]++;
                mp[{i+1,j}]++;
                mp[{i+2,j}]++;
            }
        }
    }
    
    priority_queue <pair<int, tuple<pair<int,int>, pair<int,int>, pair<int,int>>>> q;
    
    // Horizontal checks for queue insertion
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m-2; j++){
            if(a[i][j]==0 and a[i][j+1]==1 and a[i][j+2]==2){
                int temp = 1 + mp[{i,j}]-1 + mp[{i,j+1}]-1 + mp[{i,j+2}]-1;
                q.push({temp, make_tuple(make_pair(i,j), make_pair(i,j+1), make_pair(i,j+2))});
            }
        }
    }
    
    // Vertical checks for queue insertion
    for(int i=1; i<=n-2; i++){
        for(int j=1; j<=m; j++){
            if(a[i][j]==0 and a[i+1][j]==1 and a[i+2][j]==2){
                int temp = 1 + mp[{i,j}]-1 + mp[{i+1,j}]-1 + mp[{i+2,j}]-1;
                q.push({temp, make_tuple(make_pair(i,j), make_pair(i+1,j), make_pair(i+2,j))});
            }
        }
    }
    
    int ans=0;
    while(!q.empty()){
        auto top_element = q.top();
        int mx = top_element.first;
        if(mx==1) break;
        q.pop();
        
        pair<int, int> first_tuple = get<0>(top_element.second);
        pair<int, int> second_tuple = get<1>(top_element.second);
        pair<int, int> third_tuple = get<2>(top_element.second);

        int temp = 1 + mp[first_tuple]-1 + mp[second_tuple]-1 + mp[third_tuple]-1;
        if(temp != mx){
            q.push({temp, top_element.second});
            continue;
        }
        
        mp[first_tuple]--;
        mp[second_tuple]--;
        mp[third_tuple]--;
    }
    
    cout<<q.size();
}

signed main() {
    fast_io;
    int tc = 1;
    while (tc--)
        solve();
}

Compilation message (stderr)

dango_maker.cpp: In function 'void solve()':
dango_maker.cpp:85:9: warning: unused variable 'ans' [-Wunused-variable]
   85 |     int ans=0;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...