oj.uz

Submission #64514

# Submission time Handle Problem Language Result Execution time Memory
64514 2018-08-04T17:43:32 Z theknife2001 Jetpack (COCI16_jetpack) C++17
80 / 80
 76 ms 17332 KB 
#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

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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 8952 KB Output is correct
2 Correct 11 ms 9084 KB Output is correct
3 Correct 12 ms 9252 KB Output is correct
4 Correct 10 ms 9252 KB Output is correct
5 Correct 14 ms 9624 KB Output is correct
6 Correct 15 ms 9888 KB Output is correct
7 Correct 22 ms 10968 KB Output is correct
8 Correct 43 ms 13200 KB Output is correct
9 Correct 62 ms 15352 KB Output is correct
10 Correct 76 ms 17332 KB Output is correct