oj.uz

Submission #49102

# Submission time Handle Problem Language Result Execution time Memory
49102 2018-05-22T05:56:17 Z hamzqq9 Last supper (IOI12_supper) C++14
100 / 100
 299 ms 28880 KB 
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define pll pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1050000000
#define MAXN 200005
#define LOG 20
#define magic 100
#define KOK 700
#define EPS 0.0025
#define pw(x) (1<<(x))
#define PI 3.1415926535
//#include "grader.h"
using namespace std;
#include "advisor.h"

static int act[MAXN];

void ComputeAdvice(int *C, int N, int K, int M) {

  memset(act,0,sizeof(act));

  vector<int> v;

  int last[MAXN],nxt[MAXN],prv[MAXN];

  for(int i=0;i<K;i++) v.pb(i);

  for(int i=0;i<N;i++) v.pb(C[i]);

  int sz=N+K;

  memset(last,-1,sizeof(last));

  for(int i=sz-1;i>=0;i--) {

    if(~last[v[i]]) {

      nxt[i]=last[v[i]];

    }
    else {

      nxt[i]=sz;

    }

    last[v[i]]=i;

  }

  memset(last,-1,sizeof(last));

  for(int i=0;i<sz;i++) {

    if(~last[v[i]]) {

      prv[i]=last[v[i]];

    }
    else {

      prv[i]=-1;

    }

    last[v[i]]=i;

  }

  set<ii> s;

  for(int i=0;i<sz;i++) {

    if(sz(s)<K) {

      s.insert({nxt[i],v[i]});

    }
    else {

      auto plc=s.find({i,v[i]});

      if(plc!=s.end()) {

        if(prv[i]!=-1) act[prv[i]]=1;

        s.erase(plc);

      }
      else {

        auto it=prev(s.end());

        s.erase(it);

      }

      s.insert({nxt[i],v[i]});

    }

  } 

  for(int i=0;i<sz;i++) {

    WriteAdvice(act[i]);

  }

}
#include<bits/stdc++.h>
#define lf double
#define ll long long
#define cc pair<char,char>
#define ull unsigned ll
#define ii pair<int,int>
#define li pair<ll,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define iiii2 pair<int,iii>
#define lii pair<ll,ii>
#define pll pair<ll,ll>
#define heap priority_queue
#define mp make_pair
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define all(x) x.begin(),x.end()
#define len(x) strlen(x)
#define sz(x) (int) x.size()
#define orta ((bas+son)/2)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define MOD 1000000007
#define inf 1050000000
#define MAXN 200005
#define LOG 20
#define magic 100
#define KOK 700
#define EPS 0.0025
#define pw(x) (1<<(x))
#define PI 3.1415926535
//#include "grader.h"
using namespace std;
#include "assistant.h"

void Assist(unsigned char *A, int N, int K, int R) {

  set<int> del,alle;

  for(int i=0;i<K;i++) {

    if(!A[i]) {

      del.insert(i);

    }

    alle.insert(i);

  }

  for(int i=0;i<N;i++) {

    int want=GetRequest();
    unsigned char now=A[i+K];

    if(now) {

      if(alle.find(want)==alle.end()) {
      
        alle.insert(want); 

        int val=*del.begin();

        del.erase(del.begin());

        alle.erase(alle.find(val));

        PutBack(val);

      }

    } 
    else {

      if(alle.find(want)==alle.end()) {

        alle.insert(want); 

        int val=*del.begin();

        del.erase(del.begin());

        alle.erase(alle.find(val));

        PutBack(val);

      }

      del.insert(want);

    }

  }

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3824 KB Output is correct
2 Correct 6 ms 3936 KB Output is correct
3 Correct 8 ms 4168 KB Output is correct
4 Correct 9 ms 4424 KB Output is correct
5 Correct 11 ms 4488 KB Output is correct
6 Correct 13 ms 4584 KB Output is correct
7 Correct 11 ms 4624 KB Output is correct
8 Correct 11 ms 4624 KB Output is correct
9 Correct 12 ms 4928 KB Output is correct
10 Correct 13 ms 4960 KB Output is correct
11 Correct 12 ms 4960 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5160 KB Output is correct
2 Correct 84 ms 6832 KB Output is correct
3 Correct 239 ms 12496 KB Output is correct
4 Correct 129 ms 12496 KB Output is correct
5 Correct 146 ms 12496 KB Output is correct
6 Correct 162 ms 12584 KB Output is correct
7 Correct 178 ms 15744 KB Output is correct
8 Correct 162 ms 16272 KB Output is correct
9 Correct 101 ms 16272 KB Output is correct
10 Correct 299 ms 20016 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 20016 KB Output is correct
2 Correct 208 ms 20016 KB Output is correct
3 Correct 201 ms 20800 KB Output is correct
4 Correct 205 ms 21640 KB Output is correct
5 Correct 167 ms 22600 KB Output is correct
6 Correct 196 ms 24368 KB Output is correct
7 Correct 190 ms 25104 KB Output is correct
8 Correct 203 ms 26264 KB Output is correct
9 Correct 212 ms 27400 KB Output is correct
10 Correct 210 ms 28808 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28808 KB Output is correct
2 Correct 18 ms 28808 KB Output is correct
3 Correct 9 ms 28808 KB Output is correct
4 Correct 9 ms 28808 KB Output is correct
5 Correct 10 ms 28808 KB Output is correct
6 Correct 12 ms 28808 KB Output is correct
7 Correct 12 ms 28808 KB Output is correct
8 Correct 11 ms 28808 KB Output is correct
9 Correct 18 ms 28808 KB Output is correct
10 Correct 18 ms 28808 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 208 ms 28808 KB Output is correct - 120000 bits used
2 Correct 223 ms 28808 KB Output is correct - 122000 bits used
3 Correct 218 ms 28808 KB Output is correct - 125000 bits used
4 Correct 203 ms 28808 KB Output is correct - 125000 bits used
5 Correct 193 ms 28808 KB Output is correct - 125000 bits used
6 Correct 212 ms 28808 KB Output is correct - 125000 bits used
7 Correct 230 ms 28808 KB Output is correct - 124828 bits used
8 Correct 229 ms 28808 KB Output is correct - 124910 bits used
9 Correct 279 ms 28808 KB Output is correct - 125000 bits used
10 Correct 242 ms 28880 KB Output is correct - 125000 bits used