oj.uz

Submission #287100

# Submission time Handle Problem Language Result Execution time Memory
287100 2020-08-31T11:49:57 Z Kastanda Last supper (IOI12_supper) C++11
100 / 100
 230 ms 8436 KB 
// M
#include<bits/stdc++.h>
#include "advisor.h"
using namespace std;
void ComputeAdvice(int * C, int n, int k, int m)
{
        vector < int > Last(n, n), Nxt(n, n);
        for (int i = n - 1; i >= 0; i --)
                Nxt[i] = Last[C[i]], Last[C[i]] = i;
        set < pair < int , int > > ST;
        for (int i = 0; i < k; i ++)
                ST.insert({-Last[i], i});
        vector < int > M(n, 0);
        for (int i = 0; i < n; i ++)
        {
                if (ST.count({-i, C[i]}))
                {
                        ST.erase({-i, C[i]});
                        ST.insert({-Nxt[i], C[i]});
                        continue;
                }
                M[i] = 1;
                ST.erase(ST.begin());
                ST.insert({-Nxt[i], C[i]});
        }
        for (int i = 0; i < k; i ++)
                WriteAdvice(Last[i] < n && !M[Last[i]]);
        for (int i = 0; i < n; i ++)
                WriteAdvice(Nxt[i] < n && !M[Nxt[i]]);
        return ;
}
// M
#include<bits/stdc++.h>
#include "assistant.h"
using namespace std;
void Assist(unsigned char * A, int n, int k, int len)
{
        set < int > D, S;
        for (int i = 0; i < k; i ++)
        {
                if (A[i] == 1)
                        S.insert(i);
                else
                        D.insert(i);
        }
        for (int i = 0; i < n; i ++)
        {
                int c = GetRequest();
                if (S.count(c))
                {
                        S.erase(c);
                        if (A[k + i] == 1)
                                S.insert(c);
                        else
                                D.insert(c);
                        continue;
                }
                assert((int)D.size());
                int a = * D.begin();
                D.erase(D.begin());
                PutBack(a);
                if (A[k + i] == 1)
                        S.insert(c);
                else
                        D.insert(c);
        }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 776 KB Output is correct
2 Correct 1 ms 648 KB Output is correct
3 Correct 3 ms 784 KB Output is correct
4 Correct 4 ms 988 KB Output is correct
5 Correct 5 ms 1212 KB Output is correct
6 Correct 6 ms 1208 KB Output is correct
7 Correct 7 ms 1024 KB Output is correct
8 Correct 6 ms 1024 KB Output is correct
9 Correct 6 ms 1104 KB Output is correct
10 Correct 8 ms 1120 KB Output is correct
11 Correct 9 ms 1024 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1452 KB Output is correct
2 Correct 76 ms 3328 KB Output is correct
3 Correct 194 ms 8436 KB Output is correct
4 Correct 104 ms 5120 KB Output is correct
5 Correct 116 ms 5120 KB Output is correct
6 Correct 126 ms 5616 KB Output is correct
7 Correct 153 ms 6912 KB Output is correct
8 Correct 115 ms 6656 KB Output is correct
9 Correct 81 ms 5104 KB Output is correct
10 Correct 170 ms 7920 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 6128 KB Output is correct
2 Correct 166 ms 7424 KB Output is correct
3 Correct 179 ms 7424 KB Output is correct
4 Correct 172 ms 7416 KB Output is correct
5 Correct 161 ms 6912 KB Output is correct
6 Correct 167 ms 7440 KB Output is correct
7 Correct 164 ms 7664 KB Output is correct
8 Correct 150 ms 7664 KB Output is correct
9 Correct 151 ms 7440 KB Output is correct
10 Correct 163 ms 7664 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1176 KB Output is correct
2 Correct 6 ms 1104 KB Output is correct
3 Correct 6 ms 1220 KB Output is correct
4 Correct 5 ms 1204 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 6 ms 1204 KB Output is correct
7 Correct 7 ms 1180 KB Output is correct
8 Correct 8 ms 1024 KB Output is correct
9 Correct 8 ms 1160 KB Output is correct
10 Correct 10 ms 1496 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 7152 KB Output is correct - 120000 bits used
2 Correct 159 ms 7232 KB Output is correct - 122000 bits used
3 Correct 166 ms 7664 KB Output is correct - 125000 bits used
4 Correct 230 ms 7664 KB Output is correct - 125000 bits used
5 Correct 168 ms 7488 KB Output is correct - 125000 bits used
6 Correct 165 ms 7424 KB Output is correct - 125000 bits used
7 Correct 164 ms 7664 KB Output is correct - 124828 bits used
8 Correct 165 ms 7508 KB Output is correct - 124910 bits used
9 Correct 169 ms 7664 KB Output is correct - 125000 bits used
10 Correct 140 ms 7672 KB Output is correct - 125000 bits used