Contest Duration: ~ (local time) (140 minutes) Back to Home

Submission #3803507

Source Code Expand

Copy
```#include <bits/stdc++.h>
#include <sys/time.h>
using namespace std;

#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define repi(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define mt make_tuple
#define mp make_pair
template<class T1, class T2> bool chmin(T1 &a, T2 b) { return b < a && (a = b, true); }
template<class T1, class T2> bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using P = pair<ll, ll>;
ll ugauss(ll a, ll b) { if (!a) return 0; if (a>0^b>0) return a/b; else return (a+(a>0?-1:1))/b+1; }
ll lgauss(ll a, ll b) { if (!a) return 0; if (a>0^b>0) return (a+(a>0?-1:1))/b-1; else return a/b; }
template <typename T, typename U> ostream &operator<<(ostream &o, const pair<T, U> &v) {  o << "(" << v.first << ", " << v.second << ")"; return o; }
template<size_t...> struct seq{}; template<size_t N, size_t... Is> struct gen_seq : gen_seq<N-1, N-1, Is...>{}; template<size_t... Is> struct gen_seq<0, Is...> : seq<Is...>{};
template<class Ch, class Tr, class Tuple, size_t... Is>
void print_tuple(basic_ostream<Ch,Tr>& os, Tuple const& t, seq<Is...>){ using s = int[]; (void)s{0, (void(os << (Is == 0? "" : ", ") << get<Is>(t)), 0)...}; }
template<class Ch, class Tr, class... Args>
auto operator<<(basic_ostream<Ch, Tr>& os, tuple<Args...> const& t) -> basic_ostream<Ch, Tr>& { os << "("; print_tuple(os, t, gen_seq<sizeof...(Args)>()); return os << ")"; }
ostream &operator<<(ostream &o, const vvll &v) { rep(i, v.size()) { rep(j, v[i].size()) o << v[i][j] << " "; o << endl; } return o; }
template <typename T> ostream &operator<<(ostream &o, const vector<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T> ostream &operator<<(ostream &o, const deque<T> &v) { o << '['; rep(i, v.size()) o << v[i] << (i != v.size()-1 ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T>  ostream &operator<<(ostream &o, const unordered_set<T> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U>  ostream &operator<<(ostream &o, const map<T, U> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it << (next(it) != m.end() ? ", " : ""); o << "]";  return o; }
template <typename T, typename U, typename V>  ostream &operator<<(ostream &o, const unordered_map<T, U, V> &m) { o << '['; for (auto it = m.begin(); it != m.end(); it++) o << *it; o << "]";  return o; }
vector<int> range(const int x, const int y) { vector<int> v(y - x + 1); iota(v.begin(), v.end(), x); return v; }
template <typename T> istream& operator>>(istream& i, vector<T>& o) { rep(j, o.size()) i >> o[j]; return i;}
template <typename T, typename S, typename U> ostream &operator<<(ostream &o, const priority_queue<T, S, U> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.top(); tmp.pop(); o << x << " ";} return o; }
template <typename T> ostream &operator<<(ostream &o, const queue<T> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.front(); tmp.pop(); o << x << " ";} return o; }
template <typename T> ostream &operator<<(ostream &o, const stack<T> &v) { auto tmp = v; while (tmp.size()) { auto x = tmp.top(); tmp.pop(); o << x << " ";} return o; }
template <typename T> unordered_map<T, ll> counter(vector<T> vec){unordered_map<T, ll> ret; for (auto&& x : vec) ret[x]++; return ret;};
void vizGraph(vvll& g, int mode = 0, string filename = "out.png") { ofstream ofs("./out.dot"); ofs << "digraph graph_name {" << endl; set<P> memo; rep(i, g.size())  rep(j, g[i].size()) { if (mode && (memo.count(P(i, g[i][j])) || memo.count(P(g[i][j], i)))) continue; memo.insert(P(i, g[i][j])); ofs << "    " << i << " -> " << g[i][j] << (mode ? " [arrowhead = none]" : "")<< endl;  } ofs << "}" << endl; ofs.close(); system(((string)"dot -T png out.dot >" + filename).c_str()); }
struct timeval start; double sec() { struct timeval tv; gettimeofday(&tv, NULL); return (tv.tv_sec - start.tv_sec) + (tv.tv_usec - start.tv_usec) * 1e-6; }
size_t random_seed; struct init_{init_(){ ios::sync_with_stdio(false); cin.tie(0); gettimeofday(&start, NULL); struct timeval myTime; struct tm *time_st; gettimeofday(&myTime, NULL); time_st = localtime(&myTime.tv_sec); srand(myTime.tv_usec); random_seed = RAND_MAX / 2 + rand() / 2; }} init__;
#define ldout fixed << setprecision(40)

#define EPS (double)1e-14
#define INF (ll)1e18
#define mo  (ll)(1e9+7)

bool check(vll& a, ll b) {
//    cout << b << "######" << endl;
map<ll, ll> memo;
ll prev = INF;
for (auto x : a) {
if (prev >= x) {

//        cout << memo << endl;
auto from = memo.upper_bound(x);
auto en = memo.end();
memo.erase(from, en);

if (!memo.count(x)) {
memo[x] = 0;
} else {
memo[x]++;
}
auto now = memo.lower_bound(x);
while (1) {
if (now->first <= 0) {
//                cout << "NG" << endl;
return false;
}
if (now->second >= b) {
now->second -= b;
if (!memo.count(now->first-1)) {
memo[now->first-1] = 0;
} else {
memo[now->first-1]++;
}
now = memo.lower_bound(now->first-1);
} else {
break;
}
}
}
prev = x;
}
//                cout << "OK" << endl;
return true;
}

ll f(vll& tmp) {
ll ng = 0, ok = tmp.size()+10;
while (ok - ng > 1) {
ll mid = (ok + ng) / 2ll;
// mid進数でいけますか？
if (check(tmp, mid)) {
ok = mid;
} else {
ng = mid;
}
}
return ok;
}
int main(void) {
ll n; cin >> n;
vll a(n); cin >> a;

ll ret = f(a);
cout << ret << endl;

return 0;
}
```

#### Submission Info

Submission Time 2018-12-15 23:19:36+0900 C - Lexicographic constraints hamko C++14 (GCC 5.4.1) 0 6390 Byte WA 236 ms 1916 KB

#### Compile Error

```./Main.cpp: In function ‘void vizGraph(vvll&, int, std::string)’:
./Main.cpp:38:478: warning: ignoring return value of ‘int system(const char*)’, declared with attribute warn_unused_result [-Wunused-result]
void vizGraph(vvll& g, int mode = 0, string filename = "out.png") { ofstream ofs("./out.dot"); ofs << "digraph graph_name {" << endl; set<P> memo; rep(i, g.size())  rep(j, g[i].size()) { if (mode && (memo.count(P(i, g[i][j])) || memo.count(P(g[i][j], i)))) continue; memo.insert(P(i, g[i][j])); ofs << "    " << i << " -> " << g[i][j] << (mode ? " [arrowhead = none]" : "")<< endl;  } ofs << "}" << endl; ofs.close(); system(((string)"dot -T png out.dot >" + filename).c_str()); }
...```

#### Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
 AC × 1 WA × 1
 AC × 8 WA × 23
Set Name Test Cases
Sample sample01.txt, sample02.txt
All sample01.txt, sample02.txt, in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in26.txt, in27.txt, sample01.txt, sample02.txt
Case Name Status Exec Time Memory
in01.txt 188 ms 1916 KB
in02.txt 183 ms 1788 KB
in03.txt 186 ms 1788 KB
in04.txt 174 ms 1788 KB
in05.txt 179 ms 1788 KB
in06.txt 178 ms 1788 KB
in07.txt 174 ms 1788 KB
in08.txt 180 ms 1916 KB
in09.txt 62 ms 1788 KB
in10.txt 86 ms 1788 KB
in11.txt 98 ms 1788 KB
in12.txt 109 ms 1788 KB
in13.txt 104 ms 1788 KB
in14.txt 236 ms 1788 KB
in15.txt 19 ms 1788 KB
in16.txt 212 ms 1788 KB
in17.txt 20 ms 1788 KB
in18.txt 1 ms 256 KB
in19.txt 20 ms 1788 KB
in20.txt 110 ms 1788 KB
in21.txt 109 ms 1788 KB
in22.txt 109 ms 1788 KB
in23.txt 98 ms 1788 KB
in24.txt 112 ms 1788 KB
in25.txt 102 ms 1788 KB
in26.txt 98 ms 1788 KB
in27.txt 87 ms 1788 KB
sample01.txt 1 ms 256 KB
sample02.txt 1 ms 256 KB