Messages posted by: bedzo

#include <iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int n,niz[100000];
vector<int> a,t;
void update(int x)
{
    for(int i=x;i<=100000;i+=i&-i)
        niz[i]++;
}
int query(int x)
{
    long long sum=0;
    for(int i=x;i>0;i-=i&-i)
        sum+=niz[i];
    return sum;
}
int main()
{
    int i,j,r;
    memset(niz,0,sizeof(niz));
    long long ans=0;
    cin>>n;
    for(i=0;i<n;i++)
    {
        cin>>r;
        a.push_back(r);
    }
    t=a;
    sort(t.begin(),t.end());
    t.erase(unique(t.begin(),t.end()),t.end());
    for(i=0;i<n;i++)
            a[i]=lower_bound(t.begin(),t.end(),a[i])-t.begin();
    int rez1[100001],rez2[100001];
    for(i=0;i<a.size();i++)
    {
        a[i]++;
        update(a[i]);
        rez1[i]=query(100000)-query(a[i]);
    }
    memset(niz,0,sizeof(niz));
    for(i=a.size()-1;i>=0;i--)
    {
        update(a[i]);
        rez2[i]=query(a[i]-1);
    }
    for(i=0;i<a.size();i++)
        ans+=rez1[i]*rez2[i];
    cout<<ans<<endl;
    return 0;
}

Симнав 2 тест примера од сајтот и ми дава исти излез како и во тест примерот но не го прифаќа на сајтот. Во што е проблемот?

--- Едит
niza[100001] место 100000 требало да користам, средив.

Види дали ти е доволно голема низата...

tone wrote:Во брзината ли е ? 0,109 ?!

Па толку е и со бфс... Иста сложеност е.

Не е фората да имаш краток код...

tone wrote:Најбрз начин за Овци е класичен flood fill . Многу поедноставен од BFS, во многу помалку реда.

А со bfs не се прави flood fill нели?

)

Едно прашање, зошто Анастасија Самарџиска е поканета, која е 10 место, а пак Никола Полинцев кое е 6то место не е поканет?

kje ima li izborni natprevari ovaa godina?

Честитки до сите учесници на МОИ

)

edited

Во 100 линии код нема шанси да се заебеш со тоа, треба да си ептен труп.

Еве го средив кодот, додадов функција за да проверува дали е валидно да ги направи чекорите и плус го разделив кодот на делови за да биде појасен.

#include <iostream>
#include<sstream>
#include<cstring>
#include<string>
#include<iomanip>
#include<stdio.h>
#include<queue>
#include<vector>
#include<list>
#include<map>
#include<algorithm>
#include<cmath>
#include<math.h>
#define pb push_back
#define MS(a,y) memset(a,y,sizeof(a))
using namespace std;
int di[4]={1,-1,0,0},dj[4]={0,0,1,-1};
char mat[310][310];
int n,m,pi,pj,ei,ej,ans=999999;
int dp[310][310][4];
queue<int> qi,qj,qc,t;
void input()
{
    cin>>n>>m;
    int i,j,k,l;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
    {
        cin>>mat[i][j];
        if(mat[i][j]=='P')
        {
            pi=i;
            pj=j;
        }
        else if(mat[i][j]=='K')
        {
            ei=i;
            ej=j;
        }
    }
}

void output()
{
    for(int i=1;i<4;i++) if(dp[ei][ej][i]!=-1) ans=min(ans,dp[ei][ej][i]);
    cout<<ans<<endl;
}
bool isvalid(int r,int i, int j,int ri, int rj,int c)
{
    for(int k=1;k<=r;k++)
    {
        int ni=i+ri*k,nj=j+rj*k;
        if(ni<0 || ni>=n || nj<0 || nj>=m) return false;
        if(mat[ni][nj]=='#') return false;
    }
    return true;
}
void bfs()
{
    int i,j,k,l;

MS(dp,-1);

qi.push(pi);
    qj.push(pj);
    qc.push(0);
    t.push(1);
    dp[pi][pj][1]=0;
    int c,r;
    while(!qi.empty())
    {
        i=qi.front(),j=qj.front(),c=qc.front(),r=t.front();
        qi.pop(),qj.pop(),qc.pop(),t.pop();

for(k=0;k<4;k++)
            {
                int ni=i+di[k]*r,nj=j+dj[k]*r;
                if(isvalid(r,i,j,di[k],dj[k],c))
                    if(dp[ni][nj][r]==-1 || c+1<dp[ni][nj][r])
                    {
                        dp[ni][nj][r]=c+1;
                        qi.push(ni);
                        qj.push(nj);
                        qc.push(c+1);
                        t.push(r%3+1);
                    }
            }
    }

}
int main()
{

input();
    bfs();
    output();
    return 0;
}

и како може да го ставам линкот од викито како хиперлинк под Регионален таму?

obi1kenobi wrote:Е Беџо, извини вака, стварно убаво од тебе што ги постираш решенијата и се, ама кодот за Лавиринт ти е школски пример како не се програмира... Колку што имаш повторувања, можеш комотно да го разделиш во барем три функции и ем полесно да се чита, ем да се знае што правиш...

Вака ми е напишан кодот бидејќи повеќе време ќе изгубам да мислам функција одколку да го копирам првиот if и да додадам уште по еден if statement внатре. А ги разделив така бидејќи ако ги ставев во фор(за чекорите) ќе ми беше потешко да дебагирам, инаку забелешката ти е целосно на место. И дај ако можеш кажи (или дај код) како мислеше да го разделам на функции.

Lord_of_Life wrote:

bedzo wrote:Има ли официјални решенија за задачите?

Е ајде де, постирајте ги.

Е ајде, што ќе решам ќе постирам. Што не, друг ден

А како можам да ставам хиперлинк до страната под натпревари 2012?

Има ли официјални решенија за задачите?

@obi1kenobi

i taka go nemase debagerot...