oj.uz

Submission #121335

# Submission time Handle Problem Language Result Execution time Memory
121335 2019-06-26T10:47:32 Z MAMBA Last supper (IOI12_supper) C++17
0 / 100
 213 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]});
	}
	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) {
  assert(N + K == 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;
      assert(l < r);
      assert(mark_[q[l]]);
		PutBack(q[l]);
		mark_[q[l]] = false;
		mark_[v] = true;
      l++;
	}
}

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 47 ms 96000 KB Output is correct
2 Incorrect 44 ms 95984 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 97112 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 121 ms 104224 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 96496 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 137 ms 105712 KB Output isn't correct - not an optimal way
2 Incorrect 141 ms 106224 KB Output isn't correct - not an optimal way
3 Incorrect 132 ms 106480 KB Output isn't correct - not an optimal way
4 Incorrect 140 ms 106736 KB Output isn't correct - not an optimal way
5 Incorrect 150 ms 106536 KB Output isn't correct - not an optimal way
6 Incorrect 140 ms 106736 KB Output isn't correct - not an optimal way
7 Incorrect 143 ms 106480 KB Output isn't correct - not an optimal way
8 Incorrect 146 ms 106480 KB Output isn't correct - not an optimal way
9 Incorrect 213 ms 106624 KB Output isn't correct - not an optimal way
10 Correct 138 ms 108016 KB Output is correct - 125000 bits used