oj.uz

Submission #198146

# Submission time Handle Problem Language Result Execution time Memory
198146 2020-01-24T20:50:01 Z Benq Devil's Share (RMI19_devil) C++14
100 / 100
 403 ms 4960 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef double db; 
typedef string str; 

typedef pair<int,int> pi;
typedef pair<ll,ll> pl; 
typedef pair<ld,ld> pd; 
#define mp make_pair
#define f first
#define s second

typedef vector<int> vi; 
typedef vector<ll> vl; 
typedef vector<ld> vd; 
typedef vector<str> vs; 
typedef vector<pi> vpi;
typedef vector<pl> vpl; 
typedef vector<pd> vpd; 

#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend() 
#define rsz resize
#define ins insert 
#define ft front() 
#define bk back()
#define pf push_front 
#define pb push_back
#define eb emplace_back 
#define lb lower_bound 
#define ub upper_bound 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 2e5+5;
const ll INF = 1e18; 
const ld PI = acos((ld)-1);
const int xd[4] = {1,0,-1,0}, yd[4] = {0,1,0,-1}; 

template<class T> bool ckmin(T& a, const T& b) { 
	return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; }
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, 
	rb_tree_tag, tree_order_statistics_node_update>; 
// change null_type for map
#define ook order_of_key
#define fbo find_by_order

void treeExample() {
	Tree<int> t, t2; t.insert(8);
	auto it = t.insert(10).f; assert(it == t.lb(9));
	assert(t.ook(10) == 1); assert(t.ook(11) == 2);
	assert(*t.fbo(0) == 8);
	t.join(t2); // assuming T < T2 or T > T2, merge t2 into t
}

namespace input {
	template<class T> void re(complex<T>& x);
	template<class T1, class T2> void re(pair<T1,T2>& p);
	template<class T> void re(vector<T>& a);
	template<class T, size_t SZ> void re(array<T,SZ>& a);

	template<class T> void re(T& x) { cin >> x; }
	void re(double& x) { string t; re(t); x = stod(t); }
	void re(ld& x) { string t; re(t); x = stold(t); }
	template<class T, class... Ts> void re(T& t, Ts&... ts) { 
		re(t); re(ts...); 
	}

	template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); }
	template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); }
	template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); }
	template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); }
}

using namespace input;

namespace output {
	void pr(int x) { cout << x; }
	void pr(long x) { cout << x; }
	void pr(ll x) { cout << x; }
	void pr(unsigned x) { cout << x; }
	void pr(unsigned long x) { cout << x; }
	void pr(unsigned long long x) { cout << x; }
	void pr(float x) { cout << x; }
	void pr(double x) { cout << x; }
	void pr(ld x) { cout << x; }
	void pr(char x) { cout << x; }
	void pr(const char* x) { cout << x; }
	void pr(const string& x) { cout << x; }
	void pr(bool x) { pr(x ? "true" : "false"); }
	template<class T> void pr(const complex<T>& x) { cout << x; }
	
	template<class T1, class T2> void pr(const pair<T1,T2>& x);
	template<class T> void pr(const T& x);
	
	template<class T, class... Ts> void pr(const T& t, const Ts&... ts) { 
		pr(t); pr(ts...); 
	}
	template<class T1, class T2> void pr(const pair<T1,T2>& x) { 
		pr("{",x.f,", ",x.s,"}"); 
	}
	template<class T> void pr(const T& x) { 
		pr("{"); // const iterator needed for vector<bool>
		bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; 
		pr("}");
	}
	
	void ps() { pr("\n"); } // print w/ spaces
	template<class T, class... Ts> void ps(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); 
	}
	
	void pc() { pr("]\n"); } // debug w/ commas
	template<class T, class... Ts> void pc(const T& t, const Ts&... ts) { 
		pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); 
	}
	#define dbg(x...) pr("[",#x,"] = ["), pc(x);
}

using namespace output;

namespace io {
	void setIn(string s) { freopen(s.c_str(),"r",stdin); }
	void setOut(string s) { freopen(s.c_str(),"w",stdout); }
	void setIO(string s = "") {
		ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O
		// cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int
		if (sz(s)) { setIn(s+".in"), setOut(s+".out"); } // for USACO
	}
}

using namespace io;

int K,d[10];
vpi pre;
deque<pi> a;
str ans;

void ad(int x, int y) {
	if (mp(x,y) != pre.bk) pre.pb({x,y});
	int ind = sz(pre)-1;
	if (sz(a) && a.bk.f == ind) a.bk.s ++;
	else a.pb({ind,1});
}

int pf() {
	int res = a.ft.f; a.ft.s --;
	if (!a.ft.s) a.pop_front();
	return res;
}

void adans(int x) {
	if (x < 10) {
		ans += char('0'+x);
		return;
	}
	adans(pre[x].f), adans(pre[x].s);
}

void solve() {
	re(K); FOR(i,1,10) re(d[i]);
	int cnt = 9;
	str res;
	F0R(i,K-1) {
		while (!d[cnt]) cnt --;
		res += char('0'+cnt); d[cnt] --;
	}
	reverse(all(res));
	a = deque<pi>(); F0R(i,cnt+1) if (d[i]) a.pb({i,d[i]});
	pre = vpi(10,{-1,-1}); ans = "";
	while (sz(a) > 1) {
		auto t = a.bk; a.pop_back();
		F0R(i,t.s) {
			int x = pf();
			ad(t.f,x);
		}
	}
	F0R(i,a[0].s) adans(a[0].f);
	ans += res;
	ps(ans);
}

str get(str a, int b) {
	str res;
	F0R(i,sz(a)-b+1) ckmax(res,a.substr(i,b));
	return res;
}

int main() {
	// ios_base::sync_with_stdio(0); cin.tie(0);
	int t; re(t);
	F0R(i,t) solve();
	//ps(get("2313",2),get("3123",2));
	//ps(get("62616236261623778899",7),get("62616236261623778899",7));
	//ps(get("623616236162361778899",7),get("623616236162361778899",7));
	// you should actually read the stuff at the bottom
}

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do smth instead of nothing and stay organized
*/

Compilation message

devil.cpp: In function 'void io::setIn(std::__cxx11::string)':
devil.cpp:140:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  void setIn(string s) { freopen(s.c_str(),"r",stdin); }
                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
devil.cpp: In function 'void io::setOut(std::__cxx11::string)':
devil.cpp:141:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  void setOut(string s) { freopen(s.c_str(),"w",stdout); }
                          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 1400 KB Output is correct
2 Correct 168 ms 1252 KB Output is correct
3 Correct 148 ms 1388 KB Output is correct
4 Correct 266 ms 1400 KB Output is correct
5 Correct 28 ms 1272 KB Output is correct
6 Correct 30 ms 1276 KB Output is correct
7 Correct 35 ms 1400 KB Output is correct
8 Correct 27 ms 1712 KB Output is correct
9 Correct 30 ms 4960 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 1312 KB Output is correct
2 Correct 77 ms 1372 KB Output is correct
3 Correct 13 ms 1656 KB Output is correct
4 Correct 15 ms 1640 KB Output is correct
5 Correct 20 ms 1540 KB Output is correct

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 376 KB Output is correct
2 Correct 241 ms 1400 KB Output is correct
3 Correct 168 ms 1252 KB Output is correct
4 Correct 148 ms 1388 KB Output is correct
5 Correct 266 ms 1400 KB Output is correct
6 Correct 28 ms 1272 KB Output is correct
7 Correct 30 ms 1276 KB Output is correct
8 Correct 35 ms 1400 KB Output is correct
9 Correct 27 ms 1712 KB Output is correct
10 Correct 30 ms 4960 KB Output is correct
11 Correct 170 ms 1312 KB Output is correct
12 Correct 77 ms 1372 KB Output is correct
13 Correct 13 ms 1656 KB Output is correct
14 Correct 15 ms 1640 KB Output is correct
15 Correct 20 ms 1540 KB Output is correct
16 Correct 284 ms 1144 KB Output is correct
17 Correct 282 ms 1348 KB Output is correct
18 Correct 225 ms 1272 KB Output is correct
19 Correct 403 ms 1448 KB Output is correct
20 Correct 23 ms 1272 KB Output is correct
21 Correct 27 ms 1272 KB Output is correct
22 Correct 19 ms 1524 KB Output is correct
23 Correct 20 ms 2288 KB Output is correct