Submission #64514

#	Time	Username	Problem	Language	Result	Execution time	Memory
64514		theknife2001	Jetpack (COCI16_jetpack)	C++17	80 / 80	76 ms	17332 KiB

jetpack

#include<bits/stdc++.h>
#define ii pair<int ,int>
#define se second
#define fi first

using namespace std;
const int N=1e5+55;
char grid[11][N];
ii p[11][N];
int n;
bool q;

bool ok(int i , int j)
{
    return (grid[i][j]!='X'&&p[i][j]==ii(-1,-1)&&!q);
}
void dfs(int i , int j)
{
    if(j==n-1)
    {
        q=1;
        return ;
    }
    if(i==9)
    {
        if(ok(i,j+1))
        {
            p[i][j+1]={i,j};
            dfs(i,j+1);
        }
        if(ok(i-1,j+1))
        {
            p[i-1][j+1]={i,j};
            dfs(i-1,j+1);
        }
    }
    else if(i==0)
    {
        if(ok(i,j+1))
        {
            p[i][j+1]={i,j};
            dfs(i,j+1);
        }
        if(ok(i+1,j+1))
        {
            p[i+1][j+1]={i,j};
            dfs(i+1,j+1);
        }
    }
    else
    {
        if(ok(i+1,j+1))
        {
            p[i+1][j+1]={i,j};
            dfs(i+1,j+1);
        }
        if(ok(i-1,j+1))
        {
            p[i-1][j+1]={i,j};
            dfs(i-1,j+1);
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=0;i<10;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin>>grid[i][j];
        }
    }
    memset(p,-1,sizeof p);
    dfs(9,0);
    int i,j;
    vector < int > ans;
    int cnt;
    for(int k=0;k<10;k++)
    {
        cnt=n-1;
        i=k;
        j=n-1;
        int i2;
        ans.clear();
        while(!(i==9&&j==0))
        {
            if(i==-1||j==-1)
                break ;
            cnt--;
            if(p[i][j].fi>i||(i==0&&p[i][j].fi==i))
                ans.push_back(cnt);
            i2=p[i][j].fi;
            j=p[i][j].se;
            i=i2;
        }
        if(i==9&&j==0)
            break;

    }
    sort(ans.begin(),ans.end());
    int x=1;
    for(int i=1;i<ans.size();i++)
    {
        if(ans[i]!=ans[i-1]+1)
            x++;
    }
    cout<<x<<endl;
    int y;
    for(int i=0;i<ans.size();i++)
    {
        if(!i)
            x=ans[i],y=1;
        else if(ans[i]!=ans[i-1]+1)
        {
            cout<<x<<' '<<y<<endl;
            x=ans[i];
            y=1;
        }
        else
            y++;
    }
    cout<<x<<' '<<y<<endl;
    return 0;
}

Compilation message (stderr)

jetpack.cpp: In function 'int main()':
jetpack.cpp:105:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<ans.size();i++)
                 ~^~~~~~~~~~~
jetpack.cpp:112:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ans.size();i++)
                 ~^~~~~~~~~~~
jetpack.cpp:125:19: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<x<<' '<<y<<endl;
                   ^

• Subtask 1: 80 / 80