oj.uz

답안 #167226

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
167226 2019-12-06T20:22:02 Z PedroBigMan Jetpack (COCI16_jetpack) C++14
72 / 80
 1000 ms 18800 KB 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=a; i<b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define INF ((ll) pow(2,63) -1)
#define si signed
ll insig;
#define In(vecBRO, LENBRO) REP(IBRO,0,LENBRO) {cin>>insig; vecBRO.pb(insig);}
void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
ll N; vector<vector<ll> > f; vector<pl> cur; bool done;

void Endgame()
{
    vector<bool> t;
    REP(i,0,N-1) {t.pb(false);}
    REP(i,1,N)
    {
        if(cur[i-1].ff==0)
        {
            if(cur[i].ff==0) {t[i-1]=true;}
        }
        else
        {
            if(cur[i]<cur[i-1]) {t[i-1]=true;}
        }
    }
    vector<pl> ans;
    ll curs=0; ll fm=-1;
    REP(i,0,N-1)
    {
        if(t[i])
        {
            if(curs==0)
            {
                curs++;
                fm=i;
            }
            else
            {
                curs++;
            }
        }
        else
        {
            if(curs>0) 
            {
                ans.pb(mp(fm,curs));
                curs=0;
            }
        }
    }
    if(curs>0) {ans.pb(mp(fm,curs));}
    cout<<ans.size()<<endl;
    REP(i,0,ans.size())
    {
        cout<<ans[i].ff<<" "<<ans[i].ss<<endl;
    }
    
}

void DFS(ll x, ll y)
{
    if(done) {return;}
    cur.pb(mp(x,y));
    if(y==N-1)
    {
        done=true;
        Endgame();
        return;
    }
    else
    {
        pl adj;
        adj.ss=y+1;
        adj.ff=max(0LL,x-1);
        if(f[adj.ff][adj.ss]==0) {DFS(adj.ff,adj.ss);}
        adj.ff=min(9LL,x+1);
        if(f[adj.ff][adj.ss]==0) {DFS(adj.ff,adj.ss);}
    }
    cur.pop_back();
    return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    done=false;
    cin>>N;
    vector<ll> xx; REP(i,0,N) {xx.pb(0);}
    REP(i,0,10) {f.pb(xx);}
    char curc;
    REP(i,0,10)
    {
        REP(j,0,N)
        {
            cin>>curc;
            if(curc=='X') {f[i][j]=1;}
        }
    }
    DFS(9LL,0LL);
    return 0;
}

Compilation message

jetpack.cpp: In function 'void Out(std::vector<long long int>)':
jetpack.cpp:10:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
jetpack.cpp:20:29:
 void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
                             ~~~~~~~~~~~~
jetpack.cpp:20:25: note: in expansion of macro 'REP'
 void Out(vector<ll> x) {REP(i,0,x.size()) {cout<<x[i]<<" ";} cout<<endl;}
                         ^~~
jetpack.cpp: In function 'void Endgame()':
jetpack.cpp:10:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define REP(i,a,b) for(ll i=a; i<b; i++)
jetpack.cpp:65:9:
     REP(i,0,ans.size())
         ~~~~~~~~~~~~~~           
jetpack.cpp:65:5: note: in expansion of macro 'REP'
     REP(i,0,ans.size())
     ^~~

Subtask #1
72.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 4 ms 1272 KB Output is correct
6 Correct 52 ms 1656 KB Output is correct
7 Correct 228 ms 3956 KB Output is correct
8 Correct 941 ms 8876 KB Output is correct
9 Execution timed out 1074 ms 10096 KB Time limit exceeded
10 Correct 125 ms 18800 KB Output is correct