Submission #163369

#	Time	Username	Problem	Language	Result	Execution time	Memory
163369		galen_colin	Data Transfer (IOI19_transfer)	C++14	100 / 100	780 ms	2868 KiB

transfer

#include <bits/stdc++.h>
#include <chrono> 
 
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
 
#define f0r(a, b) for (long long a = 0; a < b; a++)
#define f1r(a, b, c) for (long long a = b; a < c; a++)
#define f0rd(a, b) for (long long a = b; a >= 0; a--)
#define f1rd(a, b, c) for (long long a = b; a >= c; a--)
#define ms(arr, v) memset(arr, v, sizeof(arr))
#define pb push_back
#define io {ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}
#define mp make_pair
#define f first
#define s second
#define presum(p, a, n) {p[0] = a[0]; for (int i = 1; i < n; i++) p[i] = a[i] + p[i-1];}
#define all(v) v.begin(), v.end()
#define readgraph(list, edges) for (int i = 0; i < edges; i++) {int a, b; cin >> a >> b; a--; b--; list[a].pb(b); list[b].pb(a);}
#define ai(a, n) for (int ele = 0; ele < n; ele++) cin >> a[ele];
#define ain(a, lb, rb) for (int ele = lb; ele <= rb; ele++) cin >> a[ele];
#define ao(a, n) {for (int ele = 0; ele < n; ele++) { if (ele) cout << " "; cout << a[ele]; } cout << '\n';}
#define aout(a, lb, rb) {for (int ele = lb; ele <= rb; ele++) { if (ele > lb) cout << " "; cout << a[ele]; } cout << '\n';}
typedef long long ll;
typedef double ld;
typedef long double lld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
  cout << "["; for(int i = 0; i < v.size(); i++) {if (i) cout << ", "; cout << v[i];} return cout << "]";
}
// template<typename A, typename B> ll max(A x, B y) {
//   return x > y ? x : y;
// }
// template<typename A, typename B> ll min(A x, B y) {
//   return x < y ? x : y;
// }
 
mt19937 rng(steady_clock::now().time_since_epoch().count());
/* usage - just do rng() */
 
void usaco(string filename) {
  #pragma message("be careful, freopen may be wrong")
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}
 
const ll mod = 998244353;
 
ll madd(ll a, ll b) {
  return (a + b) % mod;
}
ll msub(ll a, ll b) {
  return (((a - b) % mod) + mod) % mod;
}
ll mmul(ll a, ll b) {
  return ((a % mod) * (b % mod)) % mod;
}
ll mpow(ll base, ll exp) {
  ll res = 1;
  while (exp) {
    if (exp % 2 == 1){
        res = (res * base) % mod;
    }
    exp >>= 1;
    base = (base * base) % mod;
  }
  return res;
}
ll minv(ll base) {
  return mpow(base, mod - 2);
}
ll mdiv(ll a, ll b) {
  return mmul(a, minv(b));
}
ll gcd(ll x, ll y) {
  if (x == 0) return y;
  if (y == 0) return x;
  return gcd(y, x % y);
}
 
// bool prime[1000006]; 
// void sieve(int n) { 
//   f0r(i, n + 1) prime[i] = 1;
//   for (int p = 2; p * p <= n; p++) { 
//     if (prime[p] == true) { 
//       for (int i = p * p; i <= n; i += p) 
//         prime[i] = false; 
//     } 
//   } 
//   prime[1] = prime[0] = 0;
// } 
 
ll n, m, k, q, Q, T, l, r, x, y, z;
ll a[500005];
ll b[500005];
string s, t;
ll ans = 0;

bool pref[300];
vi ret;
vi actual;

// #include "game.h"

vector<int> get_attachment(vector<int> source) {
  n = source.size();
  ret.clear();
  
  pref[0] = 0;
  f1r(i, 1, n + 1) {
    pref[i] = pref[i - 1] ^ source[i - 1];
  }
  pref[n + 1] = pref[n];

  int sz = (n + 1) / 2;
  vi locs = {0, (int)(n + 1) / 2};
  int i = 0;
  bool fin = 0;
  while (sz) {
    bool prot = 0;
    for (int x: locs) {
      if ((x / sz) % 2) continue;
      prot ^= pref[x + sz] ^ pref[x];
    }
    fin ^= prot;
    ret.pb(prot);
    sz /= 2;
    vi o;
    for (int x: locs) o.pb(x + sz);
    for (int x: o) locs.pb(x);
  }
  ret.pb(fin);

  return ret;
}

int lg;

vector<int> retrieve(vector<int> data) {
  // cout << data << endl;
  n = 63;
  lg = 6;
  if (data.size() > 100) {
    lg = 8;
    n = 255;
  }
  else if (n == 7) lg = 3;
  bool fin = data[n + lg];
  
  bool o = 0;
  f1r(i, n, n + lg) o ^= data[i];

  actual.clear();
  if (o != fin) {
    f0r(i, n) actual.pb(data[i]);
    return actual;
  }

  pref[0] = 0;
  f1r(i, 1, n+1) {
    pref[i] = pref[i - 1] ^ data[i - 1];
  }
  pref[n + 1] = pref[n];

  int sz = (n + 1) / 2;
  vi locs = {0, (int)(n + 1) / 2};
  int i = 0;
  int l = 0, r = n;
  while (sz) {
    int m = (l + r) / 2;
    bool prot = 0;
    for (int x: locs) {
      if ((x / sz) & 1) continue;
      prot ^= pref[x + sz] ^ pref[x];
    }
    // cout << prot << " " << data[n + i] << endl;

    if (prot == data[n + i++]) l = m + 1;
    else r = m;

    // cout << l << " " << r << endl;
    sz /= 2;
    vi o;
    for (int x: locs) o.pb(x + sz);
    for (int x: o) locs.pb(x);
    // cout << sz << " " << locs << endl;
  }

  // cout << l << endl;

  data[l] = !data[l];

  f0r(i, n) actual.pb(data[i]);
  return actual;
}

// int main() {
//   io;
//   // freopen("case", "r", stdin);
//   // freopen("test.txt", "r", stdin);
//   // freopen("case", "w", stdout);
//   // freopen("file.in", "r", stdin);
 
//   // usaco("file");
//   f0r(tc, 100) {
//     vi a;
//     f0r(i, 255) a.pb(rng() % 2);
//     lg = 6;
//     vi x = get_attachment(a);
//     vi b(all(a));
//     int loc = rng() % (n + lg + 1);
//     for (int j: x) b.pb(j);
//     // cout << loc << " " << b << endl;
//     b[loc] ^= 1;
//     vi y = retrieve(b);
//     // cout << (y == a) << endl;
//     if (y != a) {
//       cout << a << endl << y << endl;
//       break;
//     }
//   }
  
// }

Compilation message (stderr)

transfer.cpp: In function 'void usaco(std::__cxx11::string)':
transfer.cpp:54:53: note: #pragma message: be careful, freopen may be wrong
   #pragma message("be careful, freopen may be wrong")
                                                     ^
transfer.cpp: In function 'std::vector<int> get_attachment(std::vector<int>)':
transfer.cpp:129:7: warning: unused variable 'i' [-Wunused-variable]
   int i = 0;
       ^
transfer.cpp: In function 'void usaco(std::__cxx11::string)':
transfer.cpp:55:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".in").c_str(), "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
transfer.cpp:56:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen((filename + ".out").c_str(), "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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