258 Alpin

[•vladrochian]

"Urmatoarele N linii contin cate N numere naturale pozitive separate prin exact un spatiu, descriind codificarea matriceala a regiunii."

[•andariel97]

De ce iau timelimit pe ultimul test? citirea: n^2, sortarea in 16385+n si dinamica in n^2

Cod:

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream fin("alpin.in");
ofstream fout("alpin.out");

int n;
int alt[1025][1025];
int sol[1025][1025];
bool ok=1;

int rezi[1025],rezj[1025];
int maxim=0;
int pozi,pozj;

struct P
{
    P(){};
    P(int _x,int _y)
    {
        x=_x;
        y=_y;
    }
    int x,y;
    int alt;
} poz[1025*1025];

void bkt(int val,int i,int j);

vector<vector<P> >S;

int main()
{
    int i,j,k=0;

    fin>>n;

    S.resize(16385);

    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        {
            fin>>alt[i][j];
            S[alt[i][j]].push_back(P(j,i));
        }

    for(i=1;i<S.size();i++)
        for(j=0;j<S[i].size();j++)
        {
            poz[k]=S[i][j];
            poz[k++].alt=i;
        }

    for(i=0;i<n*n;i++)
    {
        if(poz[i].y-1>=1)
            if(alt[poz[i].y-1][poz[i].x]>alt[poz[i].y][poz[i].x])
                if(sol[poz[i].y-1][poz[i].x]<sol[poz[i].y][poz[i].x]+1)
                {
                    sol[poz[i].y-1][poz[i].x]=sol[poz[i].y][poz[i].x]+1;
                    if(maxim<sol[poz[i].y][poz[i].x]+1)
                    {
                        maxim=sol[poz[i].y][poz[i].x]+1;
                        pozi=poz[i].y-1;
                        pozj=poz[i].x;
                    }
                }
        if(poz[i].y+1>=1)
            if(alt[poz[i].y+1][poz[i].x]>alt[poz[i].y][poz[i].x])
                if(sol[poz[i].y+1][poz[i].x]<sol[poz[i].y][poz[i].x]+1)
                {
                    sol[poz[i].y+1][poz[i].x]=sol[poz[i].y][poz[i].x]+1;
                    if(maxim<sol[poz[i].y][poz[i].x]+1)
                    {
                        maxim=sol[poz[i].y][poz[i].x]+1;
                        pozi=poz[i].y+1;
                        pozj=poz[i].x;
                    }
                }
        if(poz[i].x-1>=1)
            if(alt[poz[i].y][poz[i].x-1]>alt[poz[i].y][poz[i].x])
                if(sol[poz[i].y][poz[i].x-1]<sol[poz[i].y][poz[i].x]+1)
                {
                    sol[poz[i].y][poz[i].x-1]=sol[poz[i].y][poz[i].x]+1;
                    if(maxim<sol[poz[i].y][poz[i].x]+1)
                    {
                        maxim=sol[poz[i].y][poz[i].x]+1;
                        pozi=poz[i].y;
                        pozj=poz[i].x-1;
                    }
                }
        if(poz[i].x+1>=1)
            if(alt[poz[i].y][poz[i].x+1]>alt[poz[i].y][poz[i].x])
                if(sol[poz[i].y][poz[i].x+1]<sol[poz[i].y][poz[i].x]+1)
                {
                    sol[poz[i].y][poz[i].x+1]=sol[poz[i].y][poz[i].x]+1;
                    if(maxim<sol[poz[i].y][poz[i].x]+1)
                    {
                        maxim=sol[poz[i].y][poz[i].x]+1;
                        pozi=poz[i].y;
                        pozj=poz[i].x+1;
                    }
                }
    }

    bkt(maxim,pozi,pozj);

    rezi[maxim]=pozi;
    rezj[maxim]=pozj;

    fout<<maxim+1<<'\n';
    for(i=0;i<=maxim;i++)
        fout<<rezi[i]<<' '<<rezj[i]<<'\n';
    return 0;
}

void bkt(int val,int i,int j)
{
    for(;val!=0;val--)
    {
        if(i-1>=1)
            if(sol[i-1][j]==val-1)
            {
                rezi[val-1]=i-1;
                rezj[val-1]=j;
                i--;
                continue;
            }
        if(i+1<=n)
            if(sol[i+1][j]==val-1)
            {
                rezi[val-1]=i+1;
                rezj[val-1]=j;
                i++;
                continue;
            }
        if(j-1>=1)
            if(sol[i][j-1]==val-1)
            {
                rezi[val-1]=i;
                rezj[val-1]=j-1;
                j--;
                continue;
            }
        if(j+1<=n)
            if(sol[i][j+1]==val-1)
            {
                rezi[val-1]=i;
                rezj[val-1]=j+1;
                j++;
                continue;
            }
    }
}