oj.uz

Submission #57054

# Submission time Handle Problem Language Result Execution time Memory
57054 2018-07-13T17:16:19 Z kingpig9 Last supper (IOI12_supper) C++11
0 / 100
 710 ms 43136 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
static const int MAXN = 1e5 + 10;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

#warning static (advisor)

static int subtask;
static int *C, N, K, M;
static int logn, logk;
static set<pii> st;	//pii(when we neet i, i) -- you remove GREATEST of them.
static bool has[MAXN];
static vector<int> inds[MAXN];

static vector<int> getans() {
	//let's just implement -- get the bits
	//+ 10 just for the adjustment. Makes no difference for max values of N, K.
	logn = 31 - __builtin_clz(N + 10);
	logk = 31 - __builtin_clz(K + 10);

	for (int i = 0; i < N; i++) {
		inds[i].push_back(N);
	}
	for (int i = N - 1; i >= 0; i--) {
		inds[C[i]].push_back(i);
	}

	for (int i = 0; i < K; i++) {
		has[i] = true;
		st.emplace(inds[i].back(), i);
	}

	vector<int> ans;
	for (int i = 0; i < N; i++) {
		inds[C[i]].pop_back();
		if (has[C[i]]) {
			st.erase(pii(inds[C[i]].back(), C[i]));
			st.insert(pii(inds[C[i]].back(), C[i]));
			ans.push_back(N);	//this is bad
			debug("Bad\n");
			continue;
		}

		//remove one
		auto it = --st.end();
		pii tp = *it;
		st.erase(it);
		has[tp.se] = false;
		debug("tp.se = %d\n", tp.se);
		ans.push_back(tp.se);
		st.insert(pii(inds[C[i]].back(), C[i]));

		//add C[i]
		has[C[i]] = true;
	}
	return ans;
}

static void send (int x, int largestbit) {
	for (int i = largestbit; i >= 0; i--) {
		WriteAdvice((x >> i) & 1);
	}
}

namespace advisor_subtask2 {
	void go() {
		vector<int> ans = getans();
		//the end of computing.
		for (int x : ans) {
			send(x, logn);
		}
	}
}

namespace advisor_subtask3 {
	int where[MAXN];
	int cur[MAXN];

	void go() {
		//if < 25000
		vector<int> ans = getans();

		for (int i = 0; i < K; i++) {
			where[i] = i;
			cur[i] = i;
		}

		for (int i = 0; i < N; i++) {
			int x = ans[i];
			if (x == N) {
				//nothing changes.
				send(K, logk);
				continue;
			}
			//want to remove x
			int w = where[x];
			where[C[i]] = w;
			cur[w] = C[i];
			send(w, logk);
		}
	}
}

void ComputeAdvice (int *ccc, int nnn, int kkk, int mmm) {
	C = ccc;
	N = nnn;
	K = kkk;
	M = mmm;
	advisor_subtask3::go();
	return;


	if (M == 65000) {
		subtask = 1;
		advisor_subtask2::go();
	} else if (M == 2000000) {
		subtask = 2;
		advisor_subtask2::go();
	} else if (M == 1500000) {
		subtask = 3;
		advisor_subtask3::go();
	} else if (M == 10000) {
		subtask = 4;
	} else if (M == 1800000) {
		subtask = 5;
		advisor_subtask2::go();	//for the time being -- this gets 3 points.
	} else {
		assert(!"Bad value of M");
	}


}

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
static const int MAXN = 1e5 + 10;

#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

#warning static (assistant)

static int subtask;
static unsigned char *A;
static int N, K, R;
static int logn, logk;

namespace assistant_subtask2 {
	void go() {
		for (int i = 0; i < N; i++) {
			GetRequest();
			int x = 0;
			for (int j = 0; j <= logn; j++) {
				int pos = (logn + 1) * i + j;
				x = 2 * x + A[pos];
			}

			if (x != N) {
				PutBack(x);
			}
		}
	}
}

namespace assistant_subtask3 {
	int where[MAXN];
	int cur[MAXN];

	void go() {
		for (int i = 0; i < K; i++) {
			where[i] = i;
			cur[i] = i;
		}

		for (int i = 0; i < N; i++) {
			//replace it with this
			int req = GetRequest();
			//you replace whatever is here.
			int x = 0;
			for (int j = 0; j <= logn; j++) {
				int pos = (logn + 1) * i + j;
				x = 2 * x + A[pos];
			}

			if (x != K) {
				//then check what is here!
				//delete what is at position x, put it at
				PutBack(cur[x]);
				cur[x] = req;
				where[req] = x;
			}
		}
	}
}

void Assist (unsigned char *aaa, int nnn, int kkk, int rrr) {
	A = aaa;
	N = nnn;
	K = kkk;
	R = rrr;
	logn = 31 - __builtin_clz(N + 10);
	logk = 31 - __builtin_clz(K + 10);
	assistant_subtask3::go();
	return;


	if (N <= 5000 && R <= 65000) {
		subtask = 1;
		assistant_subtask3::go();
	} else if (N <= 100000 && R <= 2000000) {
		subtask = 2;
		assistant_subtask3::go();
	} else if (N <= 100000 && K <= 25000 && R <= 1500000) {
		subtask = 3;
		assistant_subtask3::go();
	} else if (N <= 5000 && R <= 10000) {
		subtask = 4;
	} else if (N <= 100000 && K <= 25000 && R <= 1800000) {
		subtask = 5;
		assistant_subtask3::go();	//for the time being -- this gets 3 points.
	} else {
		assert(!"Bad value of N, R");
	}
}

Compilation message

advisor.cpp:17:2: warning: #warning static (advisor) [-Wcpp]
 #warning static (advisor)
  ^~~~~~~

assistant.cpp:17:2: warning: #warning static (assistant) [-Wcpp]
 #warning static (assistant)
  ^~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5360 KB Output is correct
2 Incorrect 9 ms 5752 KB Error - Putting back a color that is not on the scaffold
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 8136 KB Error - Putting back a color that is not on the scaffold
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 512 ms 27184 KB Error - Putting back a color that is not on the scaffold
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 27184 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 586 ms 32952 KB Error - Putting back a color that is not on the scaffold
2 Incorrect 667 ms 34616 KB Error - Putting back a color that is not on the scaffold
3 Incorrect 568 ms 36112 KB Error - Putting back a color when it is already on the scaffold
4 Incorrect 699 ms 37408 KB Error - Putting back a color when it is already on the scaffold
5 Incorrect 710 ms 39104 KB Error - Putting back a color that is not on the scaffold
6 Incorrect 622 ms 39664 KB Error - Putting back a color that is not on the scaffold
7 Incorrect 633 ms 40944 KB Error - Putting back a color when it is already on the scaffold
8 Incorrect 586 ms 41792 KB Error - Putting back a color when it is already on the scaffold
9 Incorrect 561 ms 43136 KB Error - Putting back a color when it is already on the scaffold
10 Incorrect 635 ms 43136 KB Error - Putting back a color that is not on the scaffold