oj.uz

Submission #363042

# Submission time Handle Problem Language Result Execution time Memory
363042 2021-02-05T03:24:42 Z Kevin_Zhang_TW Last supper (IOI12_supper) C++17
100 / 100
 159 ms 17424 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;

#include "advisor.h"

int nxt[MAX_N];
struct cmp {
	bool operator()(int a, int b) const{ 
		return nxt[a] < nxt[b];
	}
};
// pos of color need
vector<int> pos[MAX_N];

set<int, cmp> st;

bool suc[MAX_N], need[MAX_N];

void pushin(int id) {
	st.insert(id);
}
void kill(int id) {
	st.erase(id);
}
void popoff() {
	st.erase(prev(end(st)));
}

bool kp[MAX_N + MAX_N];
void ComputeAdvice(int *C, int N, int K, int M) {
	for (int i = 0;i < N;++i) pos[i].pb(N+i);

	for (int i = N-1;i >= 0;--i)
		pos[ C[i] ].pb(i);

	for (int i = 0;i < N;++i)
		nxt[i] = pos[i].back();

	for (int i = 0;i < K;++i) 
		pushin(i);

	for (int i = 0;i < N;++i) {
		if (suc[i] = st.count(C[i])) 
			kill(C[i]);
		else 
			popoff();

		pos[ C[i] ].pop_back();
		nxt[ C[i] ] = pos[ C[i] ].back();

		pushin(C[i]);

		DE(i, C[i], suc[i]);
	}
	for (int i = N-1;i >= 0;--i) {
		DE(i+K, i, C[i], need[C[i]]);
		kp[i + K] = need[C[i]];
		need[C[i]] = suc[i];
	}
	for (int i = K-1;i >= 0;--i) 
	   kp[i] = need[i];	
	for (int i = 0;i < N + K;++i) {
		DE(i, kp[i]);
		 WriteAdvice(kp[i]);
	}
}

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
namespace {
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 300010;
}

#include "assistant.h"

int have[MAX_N];

void popoff(int id) {
	assert(have[id]);
	have[id] = false;
	PutBack(id);
}
void Assist(unsigned char *A, int N, int K, int R) {
	for (int i = 0;i < N + K;++i)
		DE((int)A[i]);
	vector<int> gar;
	for (int i = 0;i < K;++i) {
		have[i] = true;
		if (A[i] == 0) gar.pb(i);
	}
	DE(gar.size());
	debug(AI(gar));
	for (int i = 0;i < N;++i) {
		DE(i);
	debug(AI(gar));
		int req = GetRequest();
		DE(i, have[req]);
		if (!have[req]) {
			assert(gar.size());
			popoff(gar.back()); gar.pop_back();
		}
		have[req] = true;
		if (A[i + K] == 0) gar.pb(req);
	}
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:58:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   58 |   if (suc[i] = st.count(C[i]))
      |       ~~~~~~~^~~~~~~~~~~~~~~~
advisor.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
advisor.cpp:68:3: note: in expansion of macro 'DE'
   68 |   DE(i, C[i], suc[i]);
      |   ^~
advisor.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
advisor.cpp:71:3: note: in expansion of macro 'DE'
   71 |   DE(i+K, i, C[i], need[C[i]]);
      |   ^~
advisor.cpp:14:17: warning: statement has no effect [-Wunused-value]
   14 | #define DE(...) 0
      |                 ^
advisor.cpp:78:3: note: in expansion of macro 'DE'
   78 |   DE(i, kp[i]);
      |   ^~

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
assistant.cpp:32:3: note: in expansion of macro 'DE'
   32 |   DE((int)A[i]);
      |   ^~
assistant.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
assistant.cpp:38:2: note: in expansion of macro 'DE'
   38 |  DE(gar.size());
      |  ^~
assistant.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
assistant.cpp:39:2: note: in expansion of macro 'debug'
   39 |  debug(AI(gar));
      |  ^~~~~
assistant.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
assistant.cpp:41:3: note: in expansion of macro 'DE'
   41 |   DE(i);
      |   ^~
assistant.cpp:16:20: warning: statement has no effect [-Wunused-value]
   16 | #define debug(...) 0
      |                    ^
assistant.cpp:42:2: note: in expansion of macro 'debug'
   42 |  debug(AI(gar));
      |  ^~~~~
assistant.cpp:15:17: warning: statement has no effect [-Wunused-value]
   15 | #define DE(...) 0
      |                 ^
assistant.cpp:44:3: note: in expansion of macro 'DE'
   44 |   DE(i, have[req]);
      |   ^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7992 KB Output is correct
2 Correct 6 ms 7912 KB Output is correct
3 Correct 7 ms 7920 KB Output is correct
4 Correct 8 ms 7944 KB Output is correct
5 Correct 10 ms 8096 KB Output is correct
6 Correct 10 ms 8224 KB Output is correct
7 Correct 9 ms 8236 KB Output is correct
8 Correct 10 ms 8224 KB Output is correct
9 Correct 10 ms 8096 KB Output is correct
10 Correct 11 ms 8356 KB Output is correct
11 Correct 11 ms 8236 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 8796 KB Output is correct
2 Correct 62 ms 12036 KB Output is correct
3 Correct 151 ms 17400 KB Output is correct
4 Correct 96 ms 14984 KB Output is correct
5 Correct 102 ms 15260 KB Output is correct
6 Correct 123 ms 15600 KB Output is correct
7 Correct 140 ms 16352 KB Output is correct
8 Correct 112 ms 15480 KB Output is correct
9 Correct 84 ms 15760 KB Output is correct
10 Correct 149 ms 16968 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 15176 KB Output is correct
2 Correct 152 ms 16480 KB Output is correct
3 Correct 150 ms 16584 KB Output is correct
4 Correct 151 ms 16700 KB Output is correct
5 Correct 144 ms 16808 KB Output is correct
6 Correct 150 ms 16708 KB Output is correct
7 Correct 154 ms 16848 KB Output is correct
8 Correct 129 ms 16676 KB Output is correct
9 Correct 139 ms 17424 KB Output is correct
10 Correct 147 ms 16572 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8272 KB Output is correct
2 Correct 11 ms 8232 KB Output is correct
3 Correct 9 ms 8096 KB Output is correct
4 Correct 10 ms 8096 KB Output is correct
5 Correct 10 ms 8280 KB Output is correct
6 Correct 11 ms 8224 KB Output is correct
7 Correct 12 ms 8096 KB Output is correct
8 Correct 12 ms 8236 KB Output is correct
9 Correct 11 ms 8224 KB Output is correct
10 Correct 13 ms 8488 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 16572 KB Output is correct - 120000 bits used
2 Correct 159 ms 16544 KB Output is correct - 122000 bits used
3 Correct 146 ms 16600 KB Output is correct - 125000 bits used
4 Correct 155 ms 16332 KB Output is correct - 125000 bits used
5 Correct 152 ms 16576 KB Output is correct - 125000 bits used
6 Correct 146 ms 16444 KB Output is correct - 125000 bits used
7 Correct 152 ms 16356 KB Output is correct - 124828 bits used
8 Correct 146 ms 16316 KB Output is correct - 124910 bits used
9 Correct 147 ms 16316 KB Output is correct - 125000 bits used
10 Correct 132 ms 16780 KB Output is correct - 125000 bits used