oj.uz

Submission #887370

# Submission time Handle Problem Language Result Execution time Memory
887370 2023-12-14T10:29:51 Z gustavo_d Parrots (IOI11_parrots) C++17
98 / 100
 12 ms 1624 KB 
#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MX = 7;
bool nxt(vector<int> &v) {
  if (v == vector<int> (MX, 4)) return false;
  bool eq = true;
  for (int i=0; i<MX-1; i++) {
    if (v[i] != v[i+1]) eq = false;
  }

  int diff = -1;
  if (eq) diff = 0;
  else {
    for (int i=1; i<MX; i++) {
      if (v[i] != v[i-1]) diff = i;
    }
  }

  v[diff]++;
  for (int i=diff+1; i<MX; i++) v[i] = 0;

  return true;
};

void encode(int N, int M[])
{
  vector <int> v(MX, 0);
  vector<pair<int,int>> tmp(N);
  for (int i=0; i<N; i++) tmp[i] = {M[i], i};
  sort(tmp.begin(), tmp.end());
  int cnt = 0;
  for (int idx=0; idx<N; idx++) {
    while (cnt != tmp[idx].first) {
      nxt(v);
      cnt++;
    }
    // coloca tmp[idx]
    int id = tmp[idx].second;
    for (int tag : v) {
      if (tag != 0) {
        int val = id << 2;
        val += tag - 1;
        send(val);
      }
    }
  }
}

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MX = 7;
bool next(vector<int> &v) {
  if (v == vector<int> (MX, 4)) return false;
  bool eq = true;
  for (int i=0; i<MX-1; i++) {
    if (v[i] != v[i+1]) eq = false;
  }

  int diff = -1;
  if (eq) diff = 0;
  else {
    for (int i=1; i<MX; i++) {
      if (v[i] != v[i-1]) diff = i;
    }
  }

  v[diff]++;
  for (int i=diff+1; i<MX; i++) v[i] = 0;

  return true;
};

bool cmp(int a, int b) {
  return (a & 3) > (b & 3);
}

void decode(int N, int L, int X[])
{
  sort(X, X+L, cmp); // id e depois segmento maior por menor

  vector<int> vec(MX, 0);
  map<vector<int>, int> mp;
  for (int cnt=0; cnt<=255; cnt++, next(vec)) {
    mp[vec] = cnt;
  }

  vector<vector<int>> vals(N);
  for(int i=0; i<L; i++) {
    int id = (X[i] >> 2);
    int val = ((X[i]) & 3); // 00000011
    vals[id].push_back(val+1);
  }
  for (int i=0; i<N; i++) {
    while (vals[i].size() != MX) {
      vals[i].push_back(0);
    }
    output(mp[vals[i]]);
  }
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 784 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1308 KB Output is correct
2 Correct 4 ms 1324 KB Output is correct
3 Correct 5 ms 1324 KB Output is correct
4 Correct 5 ms 1324 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1308 KB Output is correct
2 Correct 4 ms 1320 KB Output is correct
3 Correct 5 ms 1316 KB Output is correct
4 Correct 5 ms 1312 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1316 KB Output is correct
2 Correct 5 ms 1320 KB Output is correct
3 Correct 5 ms 1328 KB Output is correct
4 Correct 7 ms 1344 KB Output is correct
5 Correct 5 ms 1488 KB Output is correct
6 Correct 6 ms 1344 KB Output is correct

Subtask #5
17.0 / 19.0

# Verdict Execution time Memory Grader output
1 Partially correct 5 ms 1316 KB Output is partially correct - P = 7.000000
2 Partially correct 5 ms 1336 KB Output is partially correct - P = 7.000000
3 Partially correct 6 ms 1464 KB Output is partially correct - P = 7.000000
4 Partially correct 9 ms 1624 KB Output is partially correct - P = 7.000000
5 Partially correct 9 ms 1380 KB Output is partially correct - P = 7.000000
6 Partially correct 11 ms 1380 KB Output is partially correct - P = 7.000000
7 Partially correct 12 ms 1564 KB Output is partially correct - P = 7.000000