oj.uz

Submission #58844

# Submission time Handle Problem Language Result Execution time Memory
58844 2018-07-19T15:57:32 Z joaogui1 Last supper (IOI12_supper) C++14
0 / 100
 618 ms 148848 KB 
#include "advisor.h"
#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef pair<int, int> pii;

set<pii> s;
vector <int> ans;
queue <int> q[100100];
int sca[100100], pos[100100];

vector <int> dectobin(int n){
  vector<int> r;
  for(int i = 14; i > -1; --i)
    if((1 << i) <= n){
      r.push_back(1);
      n -= (1 << i);
    }
    else  r.push_back(0);
  return r;
}

void ComputeAdvice(int *C, int N, int K, int M){
  vector <int> aux;
  memset(pos, -1, sizeof pos);
  for(int i = 0; i < N; ++i)  q[C[i]].push(-i);
  for(int i = 0; i < N; ++i) q[i].push(-2*N);
  for(int i = 0; i < K; ++i) s.insert(pii(q[i].front(), i)), sca[i] = pos[i] = i;
  for(int i = 0; i < N; ++i){
    if(pos[C[i]] != -1){
      s.erase(pii(q[C[i]].front(), pos[C[i]]));
      q[C[i]].pop();
      s.insert(pii(q[C[i]].front(), pos[C[i]]));
    }
    else{
      sca[s.begin() -> ss] = C[i];
      pos[C[i]] = s.begin() -> ss;
      ans.push_back(s.begin() -> ss);
      q[C[i]].pop();
      s.erase(s.begin());
      s.insert(pii(q[C[i]].front(), pos[C[i]]));
    }
  }
  for(int i = 0; i < ans.size(); ++i){
    aux = dectobin(ans[i]);
    for(int j = 0; j < aux. size(); ++j)
      WriteAdvice(aux[j]);
  }
}

#include "assistant.h"
#include<bits/stdc++.h>

using namespace std;

set <int> scaf;
int sca2[100100], pos2[100100];

vector<int> bintodec(unsigned char *A, int R){
  int aux = 0;
  vector<int> r;
  for(int i = 0; i < R && A[i] != 2; ++i){
    aux += (1 << (14 - (i%15)))*(A[i] == 1);
    if((i%15) == 14){
      r.push_back(aux);
      aux = 0;
    }
  }
  return r;
}

void Assist(unsigned char *A, int N, int K, int R){
  int cnt = 0;
  memset(pos2, -1, sizeof pos2);
  vector<int> rem = bintodec(A, R);
  for(int i = 0; i < K; ++i)  scaf.insert(i), sca2[i] = pos2[i] = i;
  for(int i = 0; i < N; ++i){
    int req = GetRequest();
    if(pos2[req] != -1) continue;
    else{
      PutBack(sca2[rem[cnt]]);
      pos2[sca2[rem[cnt]]] = -1;
      sca2[rem[cnt]]  = req;
      pos2[req] = rem[cnt];
      //scaf.erase(rem[cnt]);
      //scaf.insert(req);
      ++cnt;
    }
  }
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0; i < ans.size(); ++i){
                  ~~^~~~~~~~~~~~
advisor.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int j = 0; j < aux. size(); ++j)
                    ~~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 136200 KB Output is correct
2 Correct 82 ms 136648 KB Output is correct
3 Correct 98 ms 136880 KB Output is correct
4 Incorrect 92 ms 137040 KB Error - Putting back a color that is not on the scaffold
5 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 134 ms 138136 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 144680 KB Output is correct
2 Correct 459 ms 146192 KB Output is correct
3 Correct 525 ms 146416 KB Output is correct
4 Correct 521 ms 146416 KB Output is correct
5 Incorrect 352 ms 146416 KB Output isn't correct - not an optimal way
6 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 100 ms 146416 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 447 ms 146416 KB Output isn't correct - not an optimal way
2 Partially correct 430 ms 146416 KB Output is partially correct - 742095 bits used
3 Partially correct 526 ms 146504 KB Output is partially correct - 712470 bits used
4 Partially correct 461 ms 146504 KB Output is partially correct - 712005 bits used
5 Partially correct 491 ms 146504 KB Output is partially correct - 710610 bits used
6 Partially correct 464 ms 146504 KB Output is partially correct - 712155 bits used
7 Partially correct 489 ms 146504 KB Output is partially correct - 711090 bits used
8 Partially correct 446 ms 146504 KB Output is partially correct - 713340 bits used
9 Partially correct 483 ms 146504 KB Output is partially correct - 712830 bits used
10 Partially correct 618 ms 148848 KB Output is partially correct - 1103280 bits used