oj.uz

Submission #387842

# Submission time Handle Problem Language Result Execution time Memory
387842 2021-04-09T09:30:22 Z Keshi Last supper (IOI12_supper) C++17
100 / 100
 203 ms 22624 KB 
//In the name of God
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;
     
typedef long long ll;
typedef pair<ll, ll> pll;
     
const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;
     
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()
     
ll a[maxn], ok[maxn], ptr[maxn], prio[maxn], ind[maxn], ls[maxn], msg[maxn];
vector<ll> vec[maxn];
set<pll> st;
   
void ComputeAdvice(int *c, int n, int k, int m){
   	for(ll i = 0; i < k; i++){
   		a[i] = i;
		ls[i] = i;
   		ind[i] = i;
   		ok[i] = 1;
   	}
   	for(ll i = 0; i < n; i++){
   		vec[c[i]].pb(i);
   	}
   	for(ll i = 0; i < n; i++){
   		vec[i].pb(n);
   		vec[i].pb(n);
   	}
   	for(ll i = 0; i < n; i++){
   		prio[i] = vec[i][ptr[i]++];
   		if(i < k) st.insert(Mp(-prio[i], i));
   	}
   	for(ll i = 0; i < n; i++){
   		if(ok[c[i]]){
   			st.erase(Mp(-prio[c[i]], c[i]));
   			prio[c[i]] = vec[c[i]][ptr[c[i]]++];
   			st.insert(Mp(-prio[c[i]], c[i]));
			ls[c[i]] = i + k;
   			continue;
   		}
   		ll j = st.begin()->S;
		msg[ls[j]] = 1;
   		st.erase(st.begin());
   		ok[j] = 0;
   		ok[c[i]] = 1;
   		ind[c[i]] = ind[j];
   		prio[c[i]] = vec[c[i]][ptr[c[i]]++];
   		st.insert(Mp(-prio[c[i]], c[i]));
		ls[c[i]] = i + k;
   	}
	for(ll i = 0; i < n + k; i++){
		WriteAdvice(msg[i]);
	}
}
/*int main(){
  	int c[100], n, k, m;
   	cin >> n >> k >> m;
   	for(ll i = 0; i < n; i++){
   		cin >> c[i];
   	}
   	ComputeAdvice(c, n, k, m);
}*/
//In the name of God
#include <bits/stdc++.h>
#include "assistant.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 2e5 + 100;
const ll mod = 1e9 + 7;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()

ll _ok[maxn];
 
void Assist(unsigned char *A, int n, int k, int r) {
	vector<ll> vec;
	for(ll i = 0; i < k; i++){
		if(A[i]) vec.pb(i);
		_ok[i] = 1;
	}
	for(ll i = 0; i < n; i++){
		ll x = GetRequest();
		if(_ok[x]){
			if(A[i + k]) vec.pb(x);
			continue;
		}
		ll y = vec.back();
		vec.pop_back();
		if(A[i + k]) vec.pb(x);
		PutBack(y);
		_ok[y] = 0;
		_ok[x] = 1;
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5256 KB Output is correct
2 Correct 4 ms 5256 KB Output is correct
3 Correct 6 ms 5464 KB Output is correct
4 Correct 7 ms 5780 KB Output is correct
5 Correct 8 ms 6040 KB Output is correct
6 Correct 9 ms 6088 KB Output is correct
7 Correct 10 ms 6084 KB Output is correct
8 Correct 9 ms 6212 KB Output is correct
9 Correct 9 ms 6088 KB Output is correct
10 Correct 10 ms 6172 KB Output is correct
11 Correct 10 ms 6212 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6744 KB Output is correct
2 Correct 72 ms 12472 KB Output is correct
3 Correct 203 ms 22624 KB Output is correct
4 Correct 124 ms 19352 KB Output is correct
5 Correct 125 ms 19348 KB Output is correct
6 Correct 143 ms 19816 KB Output is correct
7 Correct 172 ms 20972 KB Output is correct
8 Correct 146 ms 19980 KB Output is correct
9 Correct 96 ms 18676 KB Output is correct
10 Correct 188 ms 21988 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 17500 KB Output is correct
2 Correct 199 ms 21544 KB Output is correct
3 Correct 175 ms 21760 KB Output is correct
4 Correct 192 ms 21280 KB Output is correct
5 Correct 178 ms 20624 KB Output is correct
6 Correct 178 ms 21664 KB Output is correct
7 Correct 170 ms 21548 KB Output is correct
8 Correct 167 ms 22048 KB Output is correct
9 Correct 156 ms 21224 KB Output is correct
10 Correct 183 ms 21672 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6040 KB Output is correct
2 Correct 11 ms 6224 KB Output is correct
3 Correct 8 ms 5956 KB Output is correct
4 Correct 9 ms 6084 KB Output is correct
5 Correct 9 ms 6036 KB Output is correct
6 Correct 9 ms 6092 KB Output is correct
7 Correct 9 ms 6084 KB Output is correct
8 Correct 9 ms 6092 KB Output is correct
9 Correct 10 ms 6192 KB Output is correct
10 Correct 11 ms 6356 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 20016 KB Output is correct - 120000 bits used
2 Correct 176 ms 20140 KB Output is correct - 122000 bits used
3 Correct 195 ms 20472 KB Output is correct - 125000 bits used
4 Correct 170 ms 20448 KB Output is correct - 125000 bits used
5 Correct 176 ms 20492 KB Output is correct - 125000 bits used
6 Correct 176 ms 20632 KB Output is correct - 125000 bits used
7 Correct 169 ms 20404 KB Output is correct - 124828 bits used
8 Correct 176 ms 20468 KB Output is correct - 124910 bits used
9 Correct 199 ms 20584 KB Output is correct - 125000 bits used
10 Correct 167 ms 21028 KB Output is correct - 125000 bits used