Submission #349682

# Submission time Handle Problem Language Result Execution time Memory
349682 2021-01-18T07:21:16 Z amunduzbaev Last supper (IOI12_supper) C++14
8 / 100
172 ms 262148 KB
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif
#include "advisor.h"

using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>	
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int NN = 1e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);
int fir[NN];
vector<int> tmp[NN];
vector<int> used;
void ComputeAdvice(int *c, int n, int k, int m){
	used.assign(n, mod);
	for(int i=n-1;i>=0;i--){
		used[c[i]] = i;
		tmp[i] = used;
	}
	
	vector<int> tt, cur;
	used.assign(n, 0);
	for(int i=0;i<k;i++) { used[i] = 1; tt.pb(i); }
	
	
	for(int i=0;i<n;i++){
 		cur = tmp[i];
		if(used[c[i]]) { WriteAdvice(1); continue; }
		else WriteAdvice(0);
 		
		int l = 0, r = k-1;
		int need = tt[0], in = 0;
		
		for(int j=0;j<sz(tt);j++) if(cur[tt[j]] > cur[need]) need = tt[j], in = j;
		
		while(l < r){
			int m = (l + r +1)>>1;
			if(m <= in) { WriteAdvice(0); l = m; }
			else { WriteAdvice(1); r = m-1; }
		}
		used[c[i]] = 1;
		used[tt[in]] = 0;
		tt[in] = c[i];
	}
}

/*

4 2 12
2 0 3 0

7 2 14
1 1 2 3 1 3 2

*/
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif
#include "assistant.h"

using namespace std;
 
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define ub upper_bound
#define lb lower_bound
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(),x.rend()
#define fastios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define vll vector<ll>
#define vii vector<int>
#define vpii vector<pii>
#define vpll vector<pll>
#define cnt(a)__builtin_popcount(a)
template<class T> bool umin(T& a, const T& b) {return a > b? a = b, true:false;}
template<class T> bool umax(T& a, const T& b) {return a < b? a = b, true:false;}
 
const int NN = 1e6+5;
const int mod = 1e9+7;
const ll inf = 1e18;
const ld Pi = acos(-1);

vector<int> used;
void Assist(unsigned char *a, int n, int k, int r) {
	int last = 0;
	
	used.assign(n, 0);
	vector<int> cur(k);
	for(int i=0;i<k;i++) cur[i] = i, used[i] =1;
	
	for(int i=0;i<n;i++){
		//for(auto x:cur) cout<<x<<" ";
		//cout<<"\n";
		
		int nw = GetRequest();
		if(a[last]) { last++;  continue; }
		last++;
		
		int l = 0, r = k-1;
		while(l < r){
			int m = (l + r +1)>>1;
			//cout<<l<<" "<<r<<"\n";
			if((int)a[last]) r = m-1;
			else l = m;
			//cout<<(int)a[last]<<"\n";
			last++;
		}
		//cout<<l<<" "<<r<<"\n";
		PutBack(cur[l]);
		cur[l] = nw;
	}
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 3288 KB Output is correct
2 Correct 3 ms 3192 KB Output is correct
3 Correct 6 ms 7024 KB Output is correct
4 Correct 30 ms 38436 KB Output is correct
5 Correct 68 ms 101168 KB Output is correct
6 Correct 75 ms 101480 KB Output is correct
7 Correct 70 ms 101384 KB Output is correct
8 Correct 91 ms 101640 KB Output is correct
9 Correct 88 ms 101368 KB Output is correct
10 Correct 89 ms 101564 KB Output is correct
11 Correct 85 ms 101568 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 154 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 66040 KB Error - advice is too long
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Runtime error 157 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 158 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 152 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 153 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 161 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 172 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 151 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 158 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 151 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 157 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)