Submission #167226

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
167226	2019-12-06T20:22:02 Z	PedroBigMan	Jetpack (COCI16_jetpack)	C++14	72 / 80	1000 ms	18800 KB

jetpack

#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

#	Verdict	Execution time	Memory	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