oj.uz

Submission #49036

# Submission time Handle Problem Language Result Execution time Memory
49036 2018-05-21T13:00:48 Z hamzqq9 Last supper (IOI12_supper) C++14
43 / 100
 147 ms 12640 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 100003
#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"

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

  vector<int> v;

  int last[MAXN],nxt[MAXN],prv[MAXN];
  int act[MAXN]={0};

  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 100003
#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 6 ms 2288 KB Output is correct
2 Correct 6 ms 2704 KB Output is correct
3 Correct 7 ms 2824 KB Output is correct
4 Correct 11 ms 3208 KB Output is correct
5 Correct 10 ms 3272 KB Output is correct
6 Correct 11 ms 3384 KB Output is correct
7 Correct 10 ms 3464 KB Output is correct
8 Correct 12 ms 3512 KB Output is correct
9 Correct 13 ms 3560 KB Output is correct
10 Correct 14 ms 3896 KB Output is correct
11 Correct 13 ms 3896 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 4000 KB Output is correct
2 Correct 74 ms 6376 KB Output is correct
3 Incorrect 62 ms 12160 KB Error - advice must be 0 or 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 12160 KB Output is correct
2 Incorrect 69 ms 12160 KB Error - advice must be 0 or 1
3 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

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

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 92 ms 12160 KB Error - advice must be 0 or 1
2 Incorrect 64 ms 12280 KB Error - advice must be 0 or 1
3 Incorrect 94 ms 12480 KB Error - advice must be 0 or 1
4 Incorrect 64 ms 12480 KB Error - advice must be 0 or 1
5 Incorrect 65 ms 12480 KB Error - advice must be 0 or 1
6 Incorrect 64 ms 12480 KB Error - advice must be 0 or 1
7 Incorrect 78 ms 12480 KB Error - advice must be 0 or 1
8 Incorrect 68 ms 12480 KB Error - advice must be 0 or 1
9 Incorrect 69 ms 12640 KB Error - advice must be 0 or 1
10 Incorrect 50 ms 12640 KB Error - advice must be 0 or 1