Cod sursa(job #541879)

Utilizator ssergiussSergiu-Ioan Ungur ssergiuss Data 25 februarie 2011 14:59:00
Problema Walls Scor 10
Compilator cpp Status done
Runda Romanian Master in Mathematics and Sciences 2011, Ziua 1 Marime 2.42 kb
#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;

const char Input[] = "walls.in";
const char Output[] = "walls.out";

const int Dim = 100001;

int N, M;
vector < pair < int, pair <int, int> > > w;
vector < pair <int, int> > h[Dim];

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    bool ok;
    int i, p, x, y;
    vector < pair <int, int> > :: iterator it;

    fin >> N;
    w.resize( N );

    w[0].first = 1;
    fin >> w[0].second.first >> w[0].second.second;

    for( i = 1; i < N; ++i ) {

        w[i].first = w[i - 1].first + w[i - 1].second.first + 1;
        fin >> w[i].second.first >> w[i].second.second;
    }

    fin >> M;
    while( M-- ) {

        fin >> x >> y;
        p = -1;
        for( i = N - 1; i >= 0; --i )
            if( x > w[i].first + w[i].second.first - 1 ) {

                p = i;
                break;
            }

        if( p == -1 ) {

            fout << "MISS\n";
            continue;
        }

        for( i = p; i >= 0; --i )
            if( w[i].second.second >= y ) {

                ok = false;

                for( it = h[i].begin(); it != h[i].end(); ++it )
                    if( it->first == y ) {

                        ok = true;
                        ++it->second;

                        fout << "HIT " << w[i].first + w[i].second.first - it->second << " " << i + 1 << " ";

                        if( it->second == w[i].second.first || w[i].second.second == y ) {

                            fout << "YES\n";
                            w[i].second.second = y - 1;
                        }
                        else
                            fout << "NO\n";

                        break;
                    }

                if( ok == false ) {

                    h[i].push_back( make_pair( y, 1 ) );

                    fout << "HIT " << w[i].first + w[i].second.first - 1 << " " << i + 1 << " ";

                    if( w[i].second.first == 1 || w[i].second.second == y ) {

                        fout << "YES\n";
                        w[i].second.second = y - 1;
                    }
                    else
                        fout << "NO\n";
                }

                break;
            }
        if( i == -1 )
            fout << "MISS\n";
    }

    fin.close();
    fout.close();

    return 0;
}