Submission #847667


Source Code Expand

Copy
// {{{ by shik
#include <bits/stdc++.h>
#include <unistd.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x),end(x)
#define REP(i,n) for ( int i=0; i<int(n); i++ )
#define REP1(i,a,b) for ( int i=(a); i<=int(b); i++ )
#define FOR(it,c) for ( auto it=(c).begin(); it!=(c).end(); it++ )
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef vector<int> VI;

#ifdef SHIK
template<typename T>
void _dump( const char* s, T&& head ) { cerr<<s<<"="<<head<<endl; }

template<typename T, typename... Args>
void _dump( const char* s, T&& head, Args&&... tail ) {
    int c=0;
    while ( *s!=',' || c!=0 ) {
        if ( *s=='(' || *s=='[' || *s=='{' ) c++;
        if ( *s==')' || *s==']' || *s=='}' ) c--;
        cerr<<*s++;
    }
    cerr<<"="<<head<<", ";
    _dump(s+1,tail...);
}

#define dump(...) do { \
    fprintf(stderr, "%s:%d - ", __PRETTY_FUNCTION__, __LINE__); \
    _dump(#__VA_ARGS__, __VA_ARGS__); \
} while (0)

template<typename Iter>
ostream& _out( ostream &s, Iter b, Iter e ) {
    s<<"[";
    for ( auto it=b; it!=e; it++ ) s<<(it==b?"":" ")<<*it;
    s<<"]";
    return s;
}

template<typename A, typename B>
ostream& operator <<( ostream &s, const pair<A,B> &p ) { return s<<"("<<p.first<<","<<p.second<<")"; }
template<typename T>
ostream& operator <<( ostream &s, const vector<T> &c ) { return _out(s,ALL(c)); }
template<typename T, size_t N>
ostream& operator <<( ostream &s, const array<T,N> &c ) { return _out(s,ALL(c)); }
template<typename T>
ostream& operator <<( ostream &s, const set<T> &c ) { return _out(s,ALL(c)); }
template<typename A, typename B>
ostream& operator <<( ostream &s, const map<A,B> &c ) { return _out(s,ALL(c)); }
#else
#define dump(...)
#endif

template<typename T>
void _R( T &x ) { cin>>x; }
void _R( int &x ) { scanf("%d",&x); }
void _R( long long &x ) { scanf("%" PRId64,&x); }
void _R( double &x ) { scanf("%lf",&x); }
void _R( char &x ) { scanf(" %c",&x); }
void _R( char *x ) { scanf("%s",x); }

void R() {}
template<typename T, typename... U>
void R( T& head, U&... tail ) {
    _R(head);
    R(tail...);
}

template<typename T>
void _W( const T &x ) { cout<<x; }
void _W( const int &x ) { printf("%d",x); }
template<typename T>
void _W( const vector<T> &x ) {
    for ( auto i=x.cbegin(); i!=x.cend(); i++ ) {
        if ( i!=x.cbegin() ) putchar(' ');
        _W(*i);
    }
}

void W() {}
template<typename T, typename... U>
void W( const T& head, const U&... tail ) {
    _W(head);
    putchar(sizeof...(tail)?' ':'\n');
    W(tail...);
}

#ifdef SHIK
#define FILEIO(...)
#else
#define FILEIO(name) do {\
    freopen(name ".in","r",stdin); \
    freopen(name ".out","w",stdout); \
} while (0)
#endif

// }}}

const int N=1e5+10;

int n,m;
LL a[N],b[2*N],c[N];

LL get( LL x ) {
    int p=lower_bound(a,a+n,x)-a;
    if ( p==0 ) return x;
    LL r=x%a[p-1];
    return get(r);
}

int main() {
    R(a[0],n);
    REP1(i,1,n) R(a[i]);
    n++;
    vector<LL> v;
    REP(i,n) {
        while ( !v.empty() && a[i]<=v.back() ) v.pop_back();
        v.PB(a[i]);
    }
    dump(v);
    int on=a[0];
    n=SZ(v);
    REP(i,n) a[i]=v[i];
    b[m++]=1;
    b[m++]=a[0];
    REP1(i,1,n-1) {
        LL q=a[i]/a[i-1];
        LL r=a[i]%a[i-1];
        b[m++]=q;
        b[m++]=get(r);
    }
    dump(vector<LL>(b,b+m));
    LL r=1;
    for ( int i=m-1; i>=0; i-=2 ) {
        c[b[i]]+=r;
        r*=b[i-1];
    }
    for ( int i=on-1; i>=1; i-- ) c[i]+=c[i+1];
    REP1(i,1,on) W(c[i]);
    return 0;
}

Submission Info

Submission Time
Task E - Sequential operations on Sequence
User shik
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3666 Byte
Status
Exec Time 105 ms
Memory 5236 KB

Compile Error

./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:46: warning: format ‘%ld’ expects argument of type ‘long int*’, but argument 2 has type ‘long long int*’ [-Wformat=]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                              ^
./Main.cpp: In function ‘void _R(int&)’:
./Main.cpp:61:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( int &x ) { scanf("%d",&x); }
                                   ^
./Main.cpp: In function ‘void _R(long long int&)’:
./Main.cpp:62:47: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 void _R( long long &x ) { scanf("%" PRId64,&x); }
                                               ^
./Main.cpp: In function ‘void _R(double&)’:
./Main.cpp:63:39: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-resu...

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt
All 0 / 1400 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt 64 ms 2944 KB
02.txt 57 ms 3072 KB
03.txt 55 ms 3072 KB
04.txt 55 ms 3072 KB
05.txt 54 ms 2944 KB
06.txt 72 ms 5236 KB
07.txt 76 ms 5236 KB
08.txt 75 ms 5236 KB
09.txt 79 ms 5108 KB
10.txt 74 ms 5236 KB
11.txt 71 ms 5236 KB
12.txt 77 ms 5236 KB
13.txt 78 ms 5108 KB
14.txt 72 ms 5236 KB
15.txt 71 ms 5236 KB
16.txt 74 ms 5236 KB
17.txt 74 ms 5108 KB
18.txt 72 ms 5236 KB
19.txt 71 ms 5236 KB
20.txt 74 ms 5108 KB
21.txt 105 ms 4468 KB
22.txt 65 ms 4852 KB
23.txt 84 ms 4724 KB
24.txt 50 ms 4596 KB
25.txt 50 ms 4596 KB
26.txt 48 ms 4468 KB
27.txt 32 ms 2048 KB
28.txt 32 ms 2048 KB
29.txt 32 ms 2048 KB
30.txt 33 ms 2048 KB
31.txt 4 ms 256 KB
32.txt 15 ms 1280 KB
33.txt 4 ms 256 KB
34.txt 24 ms 2432 KB
35.txt 4 ms 256 KB
36.txt 4 ms 256 KB
s1.txt 4 ms 256 KB
s2.txt 4 ms 256 KB