oj.uz

Submission #1016931

# Submission time Handle Problem Language Result Execution time Memory
1016931 2024-07-08T15:43:18 Z lovrot Last supper (IOI12_supper) C++17
0 / 100
 102 ms 73512 KB 
#include <cstdio>
#include <vector> 
#include <set>
#include <stack>
#include <algorithm>
#include "advisor.h"
#include <cstring> 
#include <cassert>

#define X first
#define Y second
#define PB push_back

using namespace std; 

typedef pair<int, int> pii;

const int N = 1e5 + 10;

int out[N], lst[N], dea[N];

stack<int> nxt[N];
set<pii> s;

void ComputeAdvice(int *c, int n, int k, int m) {
	memset(lst, -1, sizeof(lst));

	for(int i = 0; i < n; ++i) { 
		nxt[i].push(N);
	}

	for(int i = n - 1; i >= 0; --i) { 
		nxt[c[i]].push(i);
		if(i < k) { 
			s.insert({nxt[i].top(), i});
			lst[i] = i;
		}
	}

//	WriteAdvice(0);

	for(int i = 0; i < n; ++i) {
		auto it = s.lower_bound({nxt[c[i]].top(), c[i]}); 
		nxt[c[i]].pop();
		if(it != s.end() && it->Y == c[i]) { 
			out[i] = -1;			
			s.erase(it);
		} else {
			int obr = prev(s.end())->Y;
			out[i] = obr;
			assert(lst[obr] != -1);
			dea[lst[obr]] = 1;
			s.erase({nxt[obr].top(), obr});
		}	
		s.insert({nxt[c[i]].top(), c[i]});
		lst[c[i]] = i + k;
	}

	for(auto i : s) { 
//		printf("%d %d\n", i.X, i.Y); 
		dea[lst[i.Y]] = 1;
	}

//	for(int i = 0; i < n; ++i) { 
//		printf("%d %d %d\n", c[i], out[i], lst[i]);
//	}

	for(int i = 0; i < k + n; ++i) {
//		printf("%d\n", dea[i]);
		WriteAdvice(dea[i]);
	}
}

#include <cstdio>
#include <set>
#include "assistant.h"
#include <algorithm>
#include <cassert>

using namespace std; 

typedef long long ll;
typedef pair<int, int> pii;

const int N = 1e5 + 10;

// GetRequest()
// PutBack(int x)

set<int> act[2];

void Assist(unsigned char *a, int n, int k, int r) {
	for(int i = 0; i < k; ++i) { 
		act[a[i]].insert(i);
	}

	for(int i = 0; i < n; ++i) { 
		int x = GetRequest();
		bool d = a[i + k];

		auto it = act[0].lower_bound(x);
		if(it != act[0].end() && *it == x) { 
			act[0].erase(it);
		} else {
			auto it2 = act[1].lower_bound(x);
//			assert(it2 == act[1].end() || *it2 != x);
			int out = *act[1].begin();
			act[1].erase(act[1].begin());
			PutBack(out);
		}
		act[d].insert(x);
	}
}

Compilation message

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:32:9: warning: variable 'it2' set but not used [-Wunused-but-set-variable]
   32 |    auto it2 = act[1].lower_bound(x);
      |         ^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 68464 KB Output is correct
2 Correct 31 ms 68464 KB Output is correct
3 Incorrect 29 ms 68516 KB Error - Putting back a color when it is already on the scaffold
4 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 68856 KB Error - Putting back a color when it is already on the scaffold
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 73512 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 31 ms 68792 KB Error - Putting back a color when it is already on the scaffold
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 64 ms 71000 KB Error - advice must be 0 or 1
2 Incorrect 74 ms 71116 KB Error - advice must be 0 or 1
3 Incorrect 75 ms 71116 KB Error - advice must be 0 or 1
4 Incorrect 80 ms 71324 KB Error - advice must be 0 or 1
5 Incorrect 68 ms 71344 KB Error - advice must be 0 or 1
6 Incorrect 69 ms 71408 KB Error - advice must be 0 or 1
7 Incorrect 73 ms 71092 KB Error - advice must be 0 or 1
8 Incorrect 82 ms 71204 KB Error - advice must be 0 or 1
9 Incorrect 88 ms 71248 KB Error - advice must be 0 or 1
10 Incorrect 60 ms 70956 KB Error - advice must be 0 or 1