답안 #64514

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64514	2018-08-04T17:43:32 Z	theknife2001	Jetpack (COCI16_jetpack)	C++17	80 / 80	76 ms	17332 KB

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

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

#	결과	실행 시간	메모리	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