Submission #251605

#	Time	Username	Problem	Language	Result	Execution time	Memory
251605		cjoa	Data Transfer (IOI19_transfer)	C++14	100 / 100	115 ms	2680 KiB

transfer

#include "transfer.h"

using namespace std;

#include <cstdio>
#include <cassert>

std::vector<int> get_attachment(std::vector<int> source) {
   int N = source.size();
   assert(N == 63 || N == 255);
   source.push_back(0);
   ++N;
   vector<int> res;
   for (int len = N/2; len > 0; len /= 2) {
      int bit = 0;
      for (int start = 0; start < N; start += len*2) {
         for (int i = 0; i < len; ++i)
            bit ^= source[start + i];
      }
      res.push_back(bit);
   }
   int tbit = 0;
   for (int x : res)
      tbit ^= x;
   res.push_back(tbit);
   /*
   for (int x : res)
      fprintf(stderr, "%d", x);
   fprintf(stderr, "\n");
   */
   return res;
}

std::vector<int> retrieve(std::vector<int> data) {
   assert(data.size() == 63 + 7 || data.size() == 255 + 9);

   int N, K;
   if (data.size() == 63+7)
      N = 63, K = 7;
   else
      N = 255, K = 9;

   vector<int> checkbits(data.begin()+N, data.end());
   data.erase(data.begin()+N, data.end());

   /*
   fprintf(stderr, "data:");
   for (int x : data)
      fprintf(stderr, "%d", x);
   fprintf(stderr, "\n");

   fprintf(stderr, "checkbits:");
   for (int x : checkbits)
      fprintf(stderr, "%d", x);
   fprintf(stderr, "\n");
   */

   assert((int) data.size() == N);
   assert((int) checkbits.size() == K);

   int last_bit = checkbits.back();
   checkbits.pop_back();
   --K;

   // check bit on trailer info:
   int tbit = 0;
   for (int k = 0; k < K; ++k)
      tbit ^= checkbits[k];

   if (tbit != last_bit)
      return data;

   int L = 0, R = N;
   ++N;
   for (int k = 0, len = N/2; len > 0; ++k, len /= 2) {
      assert(k < K);
      int bit = 0;
      for (int start = 0; start < N; start += len*2) {
         for (int i = 0; i < len; ++i)
            bit ^= data[start + i];
      }
   // fprintf(stderr, "k:%d  len:%d   L:%d  R:%d  bit:%d  checkbit:%d\n",
   //         k, len, L, R, bit, checkbits[k]);
      int mid = (L + R) / 2;
      if (bit != checkbits[k]) {
         R = mid;
      }
      else {
         L = mid+1;
      }
   }
// fprintf(stderr, "L: %d  R: %d\n", L, R);
   assert(L == R);
   if (L < (int) data.size())
      data[L] ^= 1;

   return data;
}

• Subtask 1: 60 / 60
• Subtask 2: 40 / 40