Submission #5704001
Source Code Expand
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>
#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
putchar('\n');
}
template<class T> struct Deque {
// deque { 0, 1, 2, 3, 4, 5,};
// fr { 2, 1, 0 } | bk { 3, 4, 5 };
vector<T> fr, bk;
Deque() { }
template<class Iter> Deque(Iter first, Iter last) : bk(first, last) {}
size_t size() const {
return fr.size() + bk.size();
}
bool empty() const {
return fr.empty() && bk.empty();
}
T& operator[](size_t i) {
if (i < fr.size()) return fr[fr.size() - 1 - i];
return bk[i - fr.size()];
}
const T& operator[](size_t i) const {
if (i < fr.size()) return fr[fr.size() - 1 - i];
return bk[i - fr.size()];
}
T& back() {
if (bk.empty()) return fr[0];
return bk.back();
}
const T& back() const {
if (bk.empty()) return fr[0];
return bk.back();
}
void push_back(const T &t) {
bk.push_back(t);
}
template<typename... Args>
void emplace_back(Args&&... args) {
bk.emplace_back(forward<Args>(args)...);
}
void pop_back() {
if (bk.empty()) {
pop_back_helper(fr, bk);
} else {
bk.pop_back();
}
}
T& front() {
if (fr.empty()) return bk[0];
return fr.back();
}
const T& front() const {
if (fr.empty()) return bk[0];
return fr.back();
}
void push_front(const T &t) {
fr.push_back(t);
}
template<typename... Args>
void emplace_front(Args&&... args) {
fr.emplace_back(forward<Args>(args)...);
}
void pop_front() {
if (fr.empty()) {
pop_back_helper(bk, fr);
} else {
fr.pop_back();
}
}
void reverse() {
swap(fr, bk);
}
static void pop_back_helper(vector<T> &fr, vector<T> &bk) {
size_t s = fr.size();
size_t t = (s-1)/2;
bk.resize(t);
for (size_t i=1; i<=t; i++) bk[t-i] = fr[i];
for (size_t i=t+1; i<s; i++) fr[i-t-1] = fr[i];
fr.resize(s-1-t);
}
struct iterator {
using difference_type = size_t;
using value_type = T;
using pointer = T*;
using reference = T&;
using iterator_category = typename vector<T>::iterator::iterator_category;
using sup_iter = typename vector<T>::iterator;
sup_iter fr_it, bk_it;
sup_iter fr_begin, bk_begin;
iterator(sup_iter fr_it_, sup_iter bk_it_, sup_iter fr_begin_, sup_iter bk_begin_) {
fr_it = fr_it_;
bk_it = bk_it_;
fr_begin = fr_begin_;
bk_begin = bk_begin_;
}
iterator& operator=(const iterator &y) {
fr_it = y.fr_it;
bk_it = y.bk_it;
fr_begin = y.fr_begin;
bk_begin = y.bk_begin;
return *this;
}
iterator& operator++() {
if (fr_it == fr_begin) ++bk_it;
else --fr_it;
return *this;
}
iterator operator++(int) {
iterator tmp = *this;
++*this;
return tmp;
}
iterator& operator--() {
if (bk_it == bk_begin) ++fr_it;
else --bk_it;
return *this;
}
iterator operator--(int) {
iterator tmp = *this;
--*this;
return tmp;
}
T& operator*() {
if (fr_it == fr_begin) return *bk_it;
else return *prev(fr_it);
}
T* operator->() {
if (fr_it == fr_begin) return bk_it;
else return prev(fr_it);
}
bool operator==(const iterator &y) const { return fr_it == y.fr_it && bk_it == y.bk_it; }
bool operator!=(const iterator &y) const { return !(*this == y); }
bool operator<(const iterator &y) const { return fr_it > y.fr_it || bk_it < y.bk_it; }
bool operator>(const iterator &y) const { return y < *this; }
bool operator<=(const iterator &y) const { return !(y < *this); }
bool operator>=(const iterator &y) const { return !(*this < y); }
size_t operator-(const iterator &y) const {
return (bk_it - y.bk_it) + (y.fr_it - fr_it);
}
iterator& operator+=(size_t k) {
size_t s = fr_it - fr_begin;
if (s >= k) {
fr_it -= k;
} else {
fr_it = fr_begin;
bk_it += k-s;
}
return *this;
}
iterator operator+(size_t k) const {
iterator it = *this;
return it += k;
}
iterator& operator-=(size_t k) {
size_t s = bk_it - bk_begin;
if (s >= k) {
bk_it -= k;
} else {
bk_it = bk_begin;
fr_it += k-s;
}
return *this;
}
iterator operator-(size_t k) const {
iterator it = *this;
return it -= k;
}
};
iterator begin() {
return iterator(fr.end(), bk.begin(), fr.begin(), bk.begin());
}
iterator end() {
return iterator(fr.begin(), bk.end(), fr.begin(), bk.begin());
}
};
int N;
const int SIZE = 1000011;
int A[200011];
void MAIN() {
scanf("%d", &N);
REP (i, N-1) scanf("%d", A+i);
Deque<int>Z;
REP (i, SIZE) Z.push_back(i);
for (int i=2; i<N-1; i++) {
for (int j=1,t=0; t<A[i]; j+=2,t++) {
Z.push_front(Z[j]);
}
while (Z.size() > SIZE) Z.pop_back();
}
int M;
scanf("%d", &M);
REP ($, M) {
int x;
int ans;
scanf("%d", &x);
if (x < SIZE) ans = Z[x];
else ans = Z.back() + x - SIZE + 1;
ans += A[0] - A[1];
printf("%d\n", ans);
}
}
int main() {
int TC = 1;
// scanf("%d", &TC);
REP (tc, TC) MAIN();
return 0;
}
Submission Info
Submission Time |
|
Task |
H - Tokaido |
User |
natsugiri |
Language |
C++14 (GCC 5.4.1) |
Score |
1600 |
Code Size |
6032 Byte |
Status |
AC |
Exec Time |
73 ms |
Memory |
12908 KB |
Compile Error
./Main.cpp: In function ‘void MAIN()’:
./Main.cpp:245:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
^
./Main.cpp:246:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
REP (i, N-1) scanf("%d", A+i);
^
./Main.cpp:257:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &M);
^
./Main.cpp:261:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
^
Judge Result
Set Name |
sample |
dataset1 |
dataset2 |
Score / Max Score |
0 / 0 |
700 / 700 |
900 / 900 |
Status |
|
|
|
Set Name |
Test Cases |
sample |
sample-01.txt, sample-02.txt |
dataset1 |
sample-01.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt |
dataset2 |
sample-01.txt, sample-02.txt, 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 02-01.txt, 02-02.txt, 02-03.txt, 02-04.txt, 02-05.txt, 02-06.txt, 02-07.txt, 02-08.txt, 02-09.txt, 02-10.txt, 02-11.txt, 02-12.txt, 02-13.txt, 02-14.txt, 02-15.txt, 02-16.txt, sample-01.txt, sample-02.txt |
Case Name |
Status |
Exec Time |
Memory |
01-01.txt |
AC |
28 ms |
11244 KB |
01-02.txt |
AC |
6 ms |
6128 KB |
01-03.txt |
AC |
12 ms |
11116 KB |
01-04.txt |
AC |
21 ms |
11500 KB |
01-05.txt |
AC |
29 ms |
12268 KB |
01-06.txt |
AC |
29 ms |
12908 KB |
01-07.txt |
AC |
17 ms |
11628 KB |
01-08.txt |
AC |
29 ms |
12268 KB |
01-09.txt |
AC |
29 ms |
11500 KB |
01-10.txt |
AC |
12 ms |
10860 KB |
01-11.txt |
AC |
15 ms |
10860 KB |
01-12.txt |
AC |
28 ms |
11372 KB |
01-13.txt |
AC |
29 ms |
11628 KB |
01-14.txt |
AC |
29 ms |
12524 KB |
01-15.txt |
AC |
29 ms |
12268 KB |
01-16.txt |
AC |
27 ms |
12012 KB |
01-17.txt |
AC |
22 ms |
7024 KB |
01-18.txt |
AC |
22 ms |
6896 KB |
01-19.txt |
AC |
22 ms |
6512 KB |
02-01.txt |
AC |
20 ms |
11884 KB |
02-02.txt |
AC |
73 ms |
11372 KB |
02-03.txt |
AC |
69 ms |
12780 KB |
02-04.txt |
AC |
68 ms |
12524 KB |
02-05.txt |
AC |
51 ms |
10732 KB |
02-06.txt |
AC |
68 ms |
12908 KB |
02-07.txt |
AC |
68 ms |
12396 KB |
02-08.txt |
AC |
53 ms |
10348 KB |
02-09.txt |
AC |
52 ms |
11756 KB |
02-10.txt |
AC |
62 ms |
12268 KB |
02-11.txt |
AC |
70 ms |
12140 KB |
02-12.txt |
AC |
69 ms |
12396 KB |
02-13.txt |
AC |
70 ms |
11500 KB |
02-14.txt |
AC |
68 ms |
12140 KB |
02-15.txt |
AC |
63 ms |
6636 KB |
02-16.txt |
AC |
62 ms |
6636 KB |
sample-01.txt |
AC |
6 ms |
5232 KB |
sample-02.txt |
AC |
6 ms |
5104 KB |