oj.uz

Submission #272184

# Submission time Handle Problem Language Result Execution time Memory
272184 2020-08-18T10:16:11 Z gs18115 Last supper (IOI12_supper) C++14
100 / 100
 194 ms 8952 KB 
#include"advisor.h"
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
void ComputeAdvice(int*C,int N,int K,int M)
{
    map<pi,int,greater<pi> >st;
    vector<int>v(N,N);
    vector<int>nx=v;
    for(int i=N;i-->0;)
        nx[i]=v[C[i]],v[C[i]]=i;
    for(int i=0;i<K;i++)
        st[pi(v[i],i)]=i;
    vector<int>adv(N+K,1);
    for(int i=0;i<N;i++)
    {
        auto it=st.find(pi(i,C[i]));
        if(it==st.end())
        {
            it=st.begin();
            adv[it->se]=0;
        }
        st.erase(it);
        st[pi(nx[i],C[i])]=K+i;
    }
    for(auto t:st)
        adv[t.se]=0;
    for(int&t:adv)
        WriteAdvice(t);
    return;
}
#include"assistant.h"
#include<iostream>
#include<vector>
#include<queue>
#include<set>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
void Assist(unsigned char*A,int N,int K,int R)
{
    set<int>v1;
    queue<int>v2;
    for(int i=0;i<K;i++)
    {
        if(A[i]==1)
            v1.ep(i);
        else
            v2.ep(i);
    }
    for(int i=0;i<N;i++)
    {
        int c=GetRequest();
        auto it=v1.find(c);
        if(it==v1.end())
        {
            PutBack(v2.front());
            v2.pop();
        }
        else
            v1.erase(it);
        if(A[i+K]==1)
            v1.ep(c);
        else
            v2.ep(c);
    }
    return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 772 KB Output is correct
2 Correct 2 ms 784 KB Output is correct
3 Correct 3 ms 784 KB Output is correct
4 Correct 5 ms 980 KB Output is correct
5 Correct 5 ms 960 KB Output is correct
6 Correct 5 ms 1212 KB Output is correct
7 Correct 7 ms 1088 KB Output is correct
8 Correct 7 ms 1088 KB Output is correct
9 Correct 6 ms 1156 KB Output is correct
10 Correct 7 ms 1280 KB Output is correct
11 Correct 7 ms 1024 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1356 KB Output is correct
2 Correct 67 ms 3104 KB Output is correct
3 Correct 163 ms 8952 KB Output is correct
4 Correct 80 ms 4352 KB Output is correct
5 Correct 87 ms 4336 KB Output is correct
6 Correct 109 ms 5104 KB Output is correct
7 Correct 153 ms 6896 KB Output is correct
8 Correct 94 ms 6896 KB Output is correct
9 Correct 73 ms 4128 KB Output is correct
10 Correct 142 ms 8376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 5872 KB Output is correct
2 Correct 194 ms 7336 KB Output is correct
3 Correct 139 ms 7664 KB Output is correct
4 Correct 163 ms 7456 KB Output is correct
5 Correct 146 ms 6896 KB Output is correct
6 Correct 152 ms 7664 KB Output is correct
7 Correct 168 ms 7488 KB Output is correct
8 Correct 129 ms 7664 KB Output is correct
9 Correct 142 ms 7664 KB Output is correct
10 Correct 143 ms 7664 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1156 KB Output is correct
2 Correct 5 ms 1088 KB Output is correct
3 Correct 5 ms 1088 KB Output is correct
4 Correct 5 ms 1220 KB Output is correct
5 Correct 5 ms 1088 KB Output is correct
6 Correct 5 ms 1088 KB Output is correct
7 Correct 7 ms 1024 KB Output is correct
8 Correct 6 ms 1024 KB Output is correct
9 Correct 7 ms 1124 KB Output is correct
10 Correct 12 ms 1536 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 6640 KB Output is correct - 120000 bits used
2 Correct 142 ms 6904 KB Output is correct - 122000 bits used
3 Correct 154 ms 7408 KB Output is correct - 125000 bits used
4 Correct 146 ms 7408 KB Output is correct - 125000 bits used
5 Correct 144 ms 7408 KB Output is correct - 125000 bits used
6 Correct 150 ms 7240 KB Output is correct - 125000 bits used
7 Correct 145 ms 7320 KB Output is correct - 124828 bits used
8 Correct 146 ms 7408 KB Output is correct - 124910 bits used
9 Correct 155 ms 7360 KB Output is correct - 125000 bits used
10 Correct 120 ms 7408 KB Output is correct - 125000 bits used