Facebook Hacker Cup Rount1 #3 DeadPixels

DeadPixels.cpp

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

typedef pair<long,long> Coordinate;

int getValue(map<Coordinate, long>_map, long x, long y){
    map<Coordinate, long>::iterator it = _map.find(make_pair(x, y));
    if(it != _map.end()){
        return it->second;
    }
    else
    {
        return 0;
    }
}

void setValue(map<Coordinate, long>&_map, long x, long y, int value){
    map<Coordinate, long>::iterator it = _map.find(make_pair(x, y));
    if(it != _map.end()){
        _map[make_pair(x, y)] += value;
    }
    else
    {
        _map[make_pair(x, y)] = 0;
        _map[make_pair(x, y)] += value;
    }
}

map<Coordinate,bool> setDeadPixelCoordinateMap(
        int a, int b, int c, int d, long W, long H, long N,
        long X, long Y){
    long tmpX, tmpY, _X, _Y;
    map<Coordinate, bool> _map;
    _X = X;
    _Y = Y;
    _map.insert(make_pair(make_pair(_X, _Y), true));
    for(long i=1; i < N; ++i){
        tmpX = (_X * a + _Y * b + 1) % W;
        tmpY = (_X * c + _Y * d + 1) % H;
        _X = tmpX;
        _Y = tmpY;
        _map.insert(make_pair(make_pair(_X, _Y), true));
    }
    return _map;
}


map<Coordinate, long> setMapNumber(
        map<Coordinate, bool>_deadPixel,
        long P, long Q,
        long W, long H
        ){
    map<Coordinate, long> _mapNumber;
    map<Coordinate, bool>::iterator it = _deadPixel.begin();
    long x, y;
    long setX, setY;
    while(it != _deadPixel.end())
    {
        x = (*it).first.first;
        y = (*it).first.second;
        if(x-(P-1)<0)
        {
            setX = 0;
        }
        else
        {
            setX = x - (P-1);
        }
        if(y-(Q-1)<0)
        {
            setY = 0;
        }
        else
        {
            setY = y - (Q - 1);
        }
        setValue(_mapNumber, setX, setY, -1);
        if(x+1 <= (W-1))
        {
            setValue(_mapNumber, x+1, setY, 1);
        }
        if(y+1 <= (H-1))
        {
            setValue(_mapNumber, setX, y+1, 1);
        }
        if(x+1 <= (W-1) && y+1 <= (H-1))
        {
            setValue(_mapNumber, x+1, y+1, -1);
        }
        ++it;
    }
    return _mapNumber;
}


long solve(map<Coordinate, long> _map, long W, long H, long P, long Q)
{
    long *tmp = new long[H]();
    long accumulation = 0;
    long count = 0;
    long hitX, hitY;
    long hitValue;
    map<Coordinate, long>::iterator it = _map.begin();
    hitX = it->first.first;
    hitY = it->first.second;
    hitValue = it->second;
    for(long x = 0; x < (W-P+1); ++x){
        accumulation = 0;
        for(long y = 0; y < (H-Q+1); ++y){
            if(x == hitX && y == hitY)
            {
                accumulation += hitValue;
                if(it!= _map.end())
                {
                    ++it;
                    hitX = it->first.first;
                    hitY = it->first.second;
                    hitValue = it->second;
                    while((hitX >= (W-P+1) || hitY >= (H-Q+1)) && it!= _map.end())
                    {
                        ++it;
                        hitX = it->first.first;
                        hitY = it->first.second;
                        hitValue = it->second;
                    }
                }
            }
            tmp[y] += accumulation;
            if(tmp[y] >= 0)
            {
                ++count;
            }
        }
    }
    return count;
}

int main(){
    int T, a, b, c, d;
    long W, H, P, Q, N, X, Y;
    scanf("%d", &T);
    for(int i = 0; i < T; ++i){
        scanf("%ld %ld %ld %ld %ld %ld %ld %d %d %d %d",
                &W, &H, &P, &Q, &N, &X, &Y, &a, &b, &c, &d);
        map<Coordinate, bool> deadPixelMap;
        map<Coordinate, long> mapNumber;
        deadPixelMap = setDeadPixelCoordinateMap(
                a, b, c, d, W, H, N, X, Y);
        mapNumber = setMapNumber(deadPixelMap,
                P, Q, W, H);
        printf("Case #%d: %ld\n", i+1, solve(mapNumber, W, H, P, Q));

    }
    return 0;
}