oj.uz

Submission #274617

# Submission time Handle Problem Language Result Execution time Memory
274617 2020-08-19T13:12:51 Z shayan_p Last supper (IOI12_supper) C++14
100 / 100
 190 ms 13016 KB 
// And you curse yourself for things you never done

#include<bits/stdc++.h>

#include "advisor.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 2e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int aft[maxn], lst[maxn];
bool ans[maxn];

void ComputeAdvice(int *a, int n, int k, int m){
    fill(lst, lst + n, n);
    for(int i = n-1; i >= 0; i--){
	aft[i] = lst[a[i]];
	lst[a[i]] = i;
    }
    map<int, int> mp; // color // position
    set<pii> st;// last // color
    for(int i = 0; i < k; i++){
	mp[i] = i;
	st.insert({lst[i], i});
    }
    for(int i = 0; i < n; i++){	
	if(mp.count(a[i])){
	    int c = mp[a[i]];
	    ans[c] = 1;
	    st.erase({i, a[i]});
	}
	else{
	    int c = st.rbegin()->S;
	    ans[mp[c]] = 0;
	    mp.erase(c);
	    st.erase(--st.end());
	}
	mp[a[i]] = i + k;
	st.insert({aft[i], a[i]});
    }
    for(pii p : mp){
	ans[p.S] = 0;
    }
    for(int i = 0; i < n+k; i++){
	WriteAdvice(ans[i]);
    }
}

// And you curse yourself for things you never done

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

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

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

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

vector<int> qu;
bool use[maxn], in[maxn];

void Assist(unsigned char *a, int n, int k, int m){
    for(int i = 0; i < n; i++){
	use[i] = a[i+k] == 1;
	in[i] = 0;
    }    
    qu.clear();
    for(int i = 0; i < k; i++){
	in[i] = 1;
	if(a[i] == 0)
	    qu.PB(i);
    }
    for(int i = 0; i < n; i++){
	int c = GetRequest();
	if(!in[c]){
	    int cc = qu.back();
	    qu.pop_back();
	    PutBack(cc);
	    in[cc] = 0;
	    in[c] = 1;
	}	    
	if(!use[i]){
	    qu.PB(c);
	}
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 904 KB Output is correct
2 Correct 1 ms 904 KB Output is correct
3 Correct 3 ms 912 KB Output is correct
4 Correct 4 ms 824 KB Output is correct
5 Correct 6 ms 1104 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 10 ms 1160 KB Output is correct
8 Correct 6 ms 1024 KB Output is correct
9 Correct 8 ms 1132 KB Output is correct
10 Correct 9 ms 1280 KB Output is correct
11 Correct 9 ms 1360 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1536 KB Output is correct
2 Correct 80 ms 4080 KB Output is correct
3 Correct 190 ms 13016 KB Output is correct
4 Correct 103 ms 6200 KB Output is correct
5 Correct 150 ms 6568 KB Output is correct
6 Correct 152 ms 7408 KB Output is correct
7 Correct 166 ms 9968 KB Output is correct
8 Correct 140 ms 9968 KB Output is correct
9 Correct 86 ms 6128 KB Output is correct
10 Correct 190 ms 12024 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 8944 KB Output is correct
2 Correct 169 ms 10736 KB Output is correct
3 Correct 175 ms 10992 KB Output is correct
4 Correct 172 ms 10992 KB Output is correct
5 Correct 162 ms 9976 KB Output is correct
6 Correct 177 ms 10992 KB Output is correct
7 Correct 175 ms 10992 KB Output is correct
8 Correct 146 ms 11248 KB Output is correct
9 Correct 172 ms 10992 KB Output is correct
10 Correct 185 ms 10992 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1108 KB Output is correct
2 Correct 8 ms 1480 KB Output is correct
3 Correct 6 ms 1204 KB Output is correct
4 Correct 6 ms 1328 KB Output is correct
5 Correct 7 ms 1208 KB Output is correct
6 Correct 6 ms 1104 KB Output is correct
7 Correct 7 ms 1280 KB Output is correct
8 Correct 9 ms 1116 KB Output is correct
9 Correct 9 ms 1280 KB Output is correct
10 Correct 10 ms 2048 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 10224 KB Output is correct - 120000 bits used
2 Correct 169 ms 10480 KB Output is correct - 122000 bits used
3 Correct 169 ms 11000 KB Output is correct - 125000 bits used
4 Correct 170 ms 10992 KB Output is correct - 125000 bits used
5 Correct 175 ms 11504 KB Output is correct - 125000 bits used
6 Correct 174 ms 10992 KB Output is correct - 125000 bits used
7 Correct 177 ms 11432 KB Output is correct - 124828 bits used
8 Correct 175 ms 10992 KB Output is correct - 124910 bits used
9 Correct 177 ms 10992 KB Output is correct - 125000 bits used
10 Correct 156 ms 11056 KB Output is correct - 125000 bits used