1674F - Desktop Rearrangement - CodeForces Solution


data structures greedy implementation *1800

Please click on ads to support us..

Python Code:

import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

n, m, q = [int(x) for x in input().split()]
board = [["."]*m for i in range(n)]
stars = 0
for i in range(n):
    board[i] = [x for x in input().decode().strip()]
    stars += board[i].count("*")
stararea = 0
cellsy = 0
cellsx = 0
while cellsx*n+cellsy < stars:
    if board[cellsy][cellsx] == "*": stararea += 1
    cellsy += 1
    if cellsy%n == 0:
        cellsy = 0
        cellsx += 1

for j in range(q):
    x, y = [int(z)-1 for z in input().split()]
    if board[x][y] == "*":
        if board[(stars-1)%n][(stars-1)//n] == "*":
            stararea -= 1
        if x+y*n < stars-1: 
            stararea -= 1
        board[x][y] = "."
        stars -= 1
    elif board[x][y] == ".":
        if board[stars%n][stars//n] == "*":
            stararea += 1
        if x+y*n <= stars: 
            stararea += 1
        board[x][y] = "*"
        stars += 1
    print(stars - stararea)
    


        

C++ Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,q;
    cin>>n>>m>>q;
    char arr[n+2][m+2];
     vector < int >mp(m + 1, 0);
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=m; j++)
        {
            cin>>arr[i][j];
            if(arr[i][j]=='*')
            {
                mp[j]++;
                cnt++;
            }
        }
    }
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        if(arr[x][y]=='.')
        {
            arr[x][y]='*';
            cnt++;
            mp[y]++;
        }
        else
        {
            arr[x][y]='.';
            cnt--;
            mp[y]--;
        }
        int ans=0;
        for(int i=1; i<=(cnt/n); i++)
        {
            int p=n-mp[i];
            ans+=p;
        }
        int col=cnt%n;
        for(int i=1; i<=n; i++)
        {
            if (col== 0) break;
            if (arr[i][(cnt/n) + 1] == '.')
            {
                ans ++;
            }
            col --;
        }
        cout<<ans<<endl;;
    }
}


Comments

Submit
0 Comments
More Questions

1196C - Robot Breakout
373A - Collecting Beats is Fun
965A - Paper Airplanes
863E - Turn Off The TV
630E - A rectangle
1104A - Splitting into digits
19C - Deletion of Repeats
1550B - Maximum Cost Deletion
1693A - Directional Increase
735D - Taxes
989A - A Blend of Springtime
339C - Xenia and Weights
608A - Saitama Destroys Hotel
1342C - Yet Another Counting Problem
548A - Mike and Fax
109A - Lucky Sum of Digits
864C - Bus
626B - Cards
1221A - 2048 Game
1374D - Zero Remainder Array
1567C - Carrying Conundrum
1029C - Maximal Intersection
922C - Cave Painting
811C - Vladik and Memorable Trip
1589C - Two Arrays
1510K - King's Task
126B - Password
462A - Appleman and Easy Task
839C - Journey
622A - Infinite Sequence