Submission #49032

# Submission time Handle Problem Language Result Execution time Memory
49032 2018-05-21T12:47:41 Z hamzqq9 Last supper (IOI12_supper) C++14
0 / 100
2500 ms 8880 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++) {

    //printf("%c\n",'0'+act[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(A[i]);

    }

    alle.insert(A[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);

    }

  }

}
# Verdict Execution time Memory Grader output
1 Correct 5 ms 2288 KB Output is correct
2 Execution timed out 2559 ms 2808 KB Time limit exceeded
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2573 ms 3392 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Execution timed out 2538 ms 8336 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 8336 KB Error - Putting back a color when it is already on the scaffold
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 56 ms 8336 KB Error - advice must be 0 or 1
2 Incorrect 60 ms 8336 KB Error - advice must be 0 or 1
3 Incorrect 64 ms 8592 KB Error - advice must be 0 or 1
4 Incorrect 66 ms 8592 KB Error - advice must be 0 or 1
5 Incorrect 70 ms 8632 KB Error - advice must be 0 or 1
6 Incorrect 72 ms 8632 KB Error - advice must be 0 or 1
7 Incorrect 72 ms 8632 KB Error - advice must be 0 or 1
8 Incorrect 69 ms 8632 KB Error - advice must be 0 or 1
9 Incorrect 77 ms 8880 KB Error - advice must be 0 or 1
10 Incorrect 57 ms 8880 KB Error - advice must be 0 or 1