oj.uz

Submission #121331

# Submission time Handle Problem Language Result Execution time Memory
121331 2019-06-26T10:40:05 Z MAMBA Last supper (IOI12_supper) C++17
0 / 100
 160 ms 108016 KB 
#include <bits/stdc++.h>
#include "advisor.h"

#define rep(i , j , k) for (int i = j; i < k; i++)

using namespace std;

constexpr int MAXN = 2e6 + 10;

int ptr[MAXN];
vector<int> come[MAXN];
bitset<MAXN> a , b, mark;
set<pair<int , int>> st;

void ComputeAdvice(int *C, int N, int K, int M) {
	rep(i , 0 , N) {
		come[i].clear();
		ptr[i] = -1;
	}
	rep(i , 0 , K)
		come[i].push_back(-1);
	rep(i , 0 , N) come[C[i]].push_back(i);
	a.reset();
	b.reset();
	mark.reset();
	rep(i , 0 , K) {
		ptr[i]++;
		mark[i] = true;
		if (ptr[i] + 1 < come[i].size())
			st.insert({-come[i][ptr[i] + 1] , i});
		else st.insert({-1e9 , i});
	}
	rep(i , 0 , N) {
		ptr[C[i]]++;
		if (mark[C[i]]) continue;
		int v = st.begin()->second;
		st.erase(st.begin());
		mark[v] = false;
      mark[C[i]] = true;
		if (come[v][ptr[v]] == -1)
			a[v] = true;
		else b[come[v][ptr[v]]] = true;
		if (ptr[C[i]] + 1 < come[C[i]].size())
			st.insert({-come[C[i]][ptr[C[i]] + 1] , C[i]});
		else st.insert({-1e9 , C[i]});
	}
	for (auto e : st) {
		int v = e.second;
		if (come[v][ptr[v]] == -1)
			a[v] = true;
		else b[come[v][ptr[v]]] = true;
	}
	rep(i , 0 , K)
		WriteAdvice(a[i] ? 1 : 0);
	rep(i , 0 , N)
		WriteAdvice(b[i] ? 1 : 0);
	return;
}

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

#define rep(i , j , k) for (int i = j; i < k; i++)

using namespace std;

constexpr int MAXN = 2e6 + 10;

bitset<MAXN> a_ , b_, mark_;
int q[MAXN], l , r;

void Assist(unsigned char *A, int N, int K, int R) {
	l = r = 0;
	mark_.reset();
	a_.reset();
	b_.reset();
	rep(i , 0 , K) mark_[i] = true;
	rep(i , 0 , K)
		if (A[i])
			a_[i] = true;
	rep(i , 0 , N)
		if (A[i + K])
			b_[i] = true;
	rep(i , 0 , K)
		if (a_[i]) q[r++] = i;
	rep(i , 0 , N) {
		int v = GetRequest();
		if (b_[i]) q[r++] = v;
      	if (mark_[v]) continue;
		PutBack(q[l]);
		mark_[q[l++]] = false;
		mark_[v] = true;
	}
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:29:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ptr[i] + 1 < come[i].size())
       ~~~~~~~~~~~^~~~~~~~~~~~~~~~
advisor.cpp:43:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (ptr[C[i]] + 1 < come[C[i]].size())
       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 95984 KB Output is correct
2 Incorrect 67 ms 96240 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 53 ms 97000 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 115 ms 104480 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 46 ms 96504 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 105888 KB Error - Putting back a color that is not on the scaffold
2 Incorrect 133 ms 105968 KB Error - Putting back a color that is not on the scaffold
3 Incorrect 137 ms 106480 KB Output isn't correct - not an optimal way
4 Incorrect 144 ms 106480 KB Output isn't correct - not an optimal way
5 Incorrect 139 ms 106736 KB Output isn't correct - not an optimal way
6 Incorrect 149 ms 106480 KB Output isn't correct - not an optimal way
7 Incorrect 160 ms 106480 KB Output isn't correct - not an optimal way
8 Incorrect 143 ms 106480 KB Output isn't correct - not an optimal way
9 Incorrect 149 ms 106424 KB Output isn't correct - not an optimal way
10 Correct 159 ms 108016 KB Output is correct - 125000 bits used