2015年3月14日 星期六

2015/03/14 Codeforces 520D. Cubes

// http://codeforces.com/problemset/problem/520/D
#include <iostream>
#include <iterator>
#include <cstdio>
#include <vector>
#include <map>
#include <set>

using namespace std;

#define MOD (int)(1e9+9)
typedef long long ll;

typedef pair<int, int> xy;
#define x first
#define y second

map<xy, int> m;
vector<int> u[200000];
vector<int> d[200000];

bool hv[200000], avail[200000];
int X[200000], Y[200000];
int Ans[200000];

int M;

set<int> s;

int cnt(int p)
{
    int re = 0;

    for(auto t:d[p])
        if( hv[t] ) re += hv[t];

    return re;
}

bool check(int p)
{
    avail[p] = true;

    for(auto t:u[p])
        if( hv[t] && cnt(t) == 1 )
            avail[p] = false;

    return avail[p];
}

void process(int p)
{
    if( !hv[p] ) return;

    if( check(p) ) s.insert(p);
    else s.erase(p);
}

int main()
{
    scanf("%d", &M);

    for(int Mi = 0; Mi < M; Mi++)
    {
        scanf("%d %d", &X[Mi], &Y[Mi]);
        m[xy(X[Mi], Y[Mi]) ] = Mi;
        hv[Mi] = true;
    }

    for(int Mi = 0; Mi < M; Mi++)
    {
        for(int i = -1; i <= 1; i++)
        {
            int nx = X[Mi]+i;
            int ny = Y[Mi]+1;

            xy pr = xy(nx, ny);

            if( m.find(pr) != m.end() )
                u[Mi].push_back(m[pr] );
        }

        for(int i = -1; i <= 1; i++)
        {
            int nx = X[Mi]+i;
            int ny = Y[Mi]-1;

            xy pr = xy(nx, ny);

            if( m.find(pr) != m.end() )
                d[Mi].push_back(m[pr] );
        }
    }



    for(int Mi = 0; Mi < M; Mi++)
        process(Mi);

    for(int Mi = 0; Mi < M; Mi++)
    {
        int rm;

        if( Mi%2 == 0 ) rm = *prev(s.end() );
        else rm = *s.begin();

        s.erase(rm);

        hv[rm] = false;
        Ans[Mi] = rm;

        for(auto t:d[rm])
            process(t);

        for(auto p:u[rm])
            for(auto t:d[p])
                process(t);
    }

    ll val = 1;
    ll num = 0;

    for(int Mi = M-1; Mi >= 0; Mi--)
    {
        num += val*Ans[Mi];
        num %= MOD;

        val *= M;
        val %= MOD;
    }

    cout<<num<<endl;
}

沒有留言:

張貼留言