oj.uz

Submission #49101

# Submission time Handle Problem Language Result Execution time Memory
49101 2018-05-22T05:54:46 Z hamzqq9 Last supper (IOI12_supper) C++14
43 / 100
 160 ms 13528 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 100005
#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) {

  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++) {

    assert(act[i]<=1);

    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 5 ms 1424 KB Output is correct
2 Correct 4 ms 1640 KB Output is correct
3 Correct 6 ms 2000 KB Output is correct
4 Correct 7 ms 2064 KB Output is correct
5 Correct 11 ms 2200 KB Output is correct
6 Correct 11 ms 2248 KB Output is correct
7 Correct 10 ms 2296 KB Output is correct
8 Correct 13 ms 2600 KB Output is correct
9 Correct 11 ms 2600 KB Output is correct
10 Correct 13 ms 2872 KB Output is correct
11 Correct 12 ms 2872 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 2920 KB Output is correct
2 Correct 73 ms 5152 KB Output is correct
3 Runtime error 37 ms 5400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 13528 KB Output is correct
2 Runtime error 61 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
35.0 / 35.0

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

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 26 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 40 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 22 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 36 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 33 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 22 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 27 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 24 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 23 ms 6764 KB Execution killed with signal 11 (could be triggered by violating memory limits)