oj.uz

Submission #23101

# Submission time Handle Problem Language Result Execution time Memory
23101 2017-05-03T05:29:21 Z model_code Gauss (COCI17_gauss) C++11
160 / 160
 1326 ms 139176 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

#define num first
#define val second
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define _ << " _ " <<
#define TRACE(x) cerr << #x << " = " << x << endl
#define debug(...) fprintf(stderr, __VA_ARGS__)
//#define debug
//#define TRACE(x)

using namespace std;
using llint = long long;
using vec = vector<int>;
using pii = pair<int, int>;

const int MAX = 1000000;
const int MAXK = 10010;
const int MAXC = 305;
const int MAXD = 6500;
const int MAXM = 55;
const int MAXLEN = 23;
const int INF = 1e9;

struct edge {
  int div, v, w;
};

struct line {
  llint k, l;
};

vector<pii> happy;
vec primes, s;
int dist[MAXC][MAXLEN], divs[MAXC], f[MAXK], K, hap[MAX + 10], price[MAX + 10];
vector<edge> edg[MAXC];

inline int get(int i) { return (i > K) ? 0 : f[i]; }

inline void add_edge(int a, int div, int b, int w) {
  edg[a].push_back({div, b, w});
  if (b == 0 && a != 0) 
    dist[a][1] = min(dist[a][1], w);
}

inline int index(int x) {
  return (int)(lower_bound(s.begin(), s.end(), x) - s.begin());
}

int compress(int n) {
  vec e;
  for (int p : primes) {
    if (p * p > n) break;
    if (n % p > 0) continue;
    int ec = 0;
    while (n % p == 0) {
      n /= p;
      ++ec;
    }
    e.push_back(ec);
  }
  if (n > 1)
    e.push_back(1);
  
  sort(e.begin(), e.end());
  reverse(e.begin(), e.end());
  
  int ret = 1;
  for (int i = 0; i < (int)e.size(); ++i)
    for (int j = 0; j < e[i]; ++j)
      ret *= primes[i];
  return ret;
}

int divisors(int n) {
  int ret = 0;
  for (int m = 1; m * m <= n; ++m)
    if (n % m == 0) {
      ++ret;
      if (m * m != n)
	++ret;
    }
  return ret;
}

bool isprime(int p) {
  for (int q = 2; q * q <= p; ++q)
    if (p % q == 0)
      return false;
  return true;
}

void gen(llint m, int i, int prv) {
  s.push_back((int)m);

  for (int x = 1; x <= prv; ++x) {
    m *= primes[i];
    if (m > MAX) break;
    gen(m, i + 1, x);
  }
}

//llint best[MAXC][MAXC][MAXM][MAXM];
llint bl[MAXD][MAXM][MAXLEN];
llint bl2[MAXD][MAXM][MAXLEN];
int idx[MAXC][MAXC];
vector<int> lens;

int sz;
line st[MAXM * MAXLEN];

double getx(line l1, line l2) {
  return (l2.l - l1.l) / (double)(l1.k - l2.k);
}

void insert(line l) {
  while (sz >= 1 && st[sz - 1].k == l.k) {
    if (st[sz - 1].l > l.l)
      --sz;
    else
      return;
  }

  while (sz >= 2 && getx(st[sz - 1], l) < getx(st[sz - 1], st[sz - 2]))
    --sz;

  st[sz++] = l;
}

void preprocess_fast() {
  int tot = 0;
  REP(x, (int)s.size()) 
    REP(y, (int)s.size()) {
      if ((llint)s[x] * s[y] > MAX) continue;
      idx[x][y] = tot++;
  }

  REP(x, (int)s.size()) {
    REP(y, (int)s.size()) {
      if ((llint)s[x] * s[y] > MAX) continue;
      for (int i = 0; i < (int)happy.size(); ++i) {
	  REP(len, MAXLEN) bl[idx[x][y]][i][len] = INF;
	  REP(len1, MAXLEN) {
	    REP(len2, MAXLEN - len1) {
	      if (dist[x][len1] != INF && dist[y][len2] != INF) {
		llint tmp = 0;
		tmp += dist[x][len1];
		tmp += dist[y][len2];
		tmp += (llint)(-len1 - len2) * happy[i].val;
		bl[idx[x][y]][i][len1 + len2] =
		  min(bl[idx[x][y]][i][len1 + len2], tmp);
	      }
	    }
	    bl2[idx[x][y]][i][0] = bl[idx[x][y]][i][0];
	    FOR(len, 1, MAXLEN)
	      bl2[idx[x][y]][i][len] =
	      min(bl2[idx[x][y]][i][len - 1], bl[idx[x][y]][i][len]);
	  }
      }
    }
  }
}

llint solve_fast2(int a, int b) {
  llint sol = 0;
  sz = 0;
  int ptr = 0;
  
  for (int j = 0; j < (int)happy.size(); ++j) {
    int c = happy[j].num;
    if (a % c != 0 || c % b != 0) continue;
    int x = index(compress(a / c));
    int y = index(compress(c / b));

    insert({happy[j].val, bl2[idx[x][y]][j][MAXLEN - 1]});
  }

  for (int i = 0; i < (int)lens.size(); ++i) {
    llint ret = INF;
    if (lens[i] < MAXLEN) {
      ret = dist[index(compress(a / b))][lens[i]];
      for (int j = 0; j < (int)happy.size(); ++j) {
	int c = happy[j].num;
	if (a % c != 0 || c % b != 0) continue;
	int x = index(compress(a / c));
	int y = index(compress(c / b));
	ret = min(ret, bl2[idx[x][y]][j][lens[i]] + (llint)lens[i] * happy[j].val);
      }
    } else {
      for (; ptr + 1 < sz && getx(st[ptr], st[ptr + 1]) < lens[i]; ++ptr);
      if (sz > 0) 
      	ret = min(ret, st[ptr].k * (llint)lens[i] + st[ptr].l);
    }
    if (ret == INF) ret = -1;
    sol += (a % b != 0) ? -1 : ret;
  }
  return sol;
}

bool cmp2(pii a, pii b) { return a.second > b.second; }

void init() {
  int M, L;
  scanf("%d",&K);
  FOR(i, 1, K + 1) scanf("%d",&f[i]);
  scanf("%d",&L);
  lens.resize(L);
  REP(i, L) scanf("%d",&lens[i]);
  sort(lens.begin(), lens.end());
  
  scanf("%d",&M);
  REP(i, M) {
    int x, cost;
    scanf("%d %d",&x,&cost);
    happy.push_back({x, cost});
    hap[x] = 1;
    price[x] = cost;
  }
  sort(happy.begin(), happy.end(), cmp2);
}

int main(void) {
  REP(a, MAXC) REP(len, MAXLEN) dist[a][len] = INF;
  dist[0][0] = 0;
  init();

  for (int p = 2; p * p <= MAX; ++p)
    if (isprime(p))
      primes.push_back(p);

  gen(1, 0, MAX);
  sort(s.begin(), s.end());
  
  REP(i, (int)s.size()) 
    divs[i] = divisors(s[i]);

  // TRACE((int)s.size());
  // TRACE((int)primes.size());

  for (int i = 0; i < (int)s.size(); ++i) {
    int a = s[i];
    for (int x = 1; x * x <= a; ++x)
      if (a % x == 0) {
	int j = index(compress(x));
	int k = index(compress(a / x));
	add_edge(i, x, j, get(divs[k]));
	if (x * x != a) 
	  add_edge(i, a / x, k, get(divs[j]));
      }
  }

  for (int len = 2; len < MAXLEN; ++len) 
    for (int x = 0; x < MAXC; ++x) 
      for (auto y : edg[x])
	if (y.v != x)
	  dist[x][len] = min(dist[x][len], dist[y.v][len - 1] + y.w);
  
  preprocess_fast();
  
  int q, A, B;
  scanf("%d",&q);
  
  REP(it, q) {
    scanf("%d %d",&A,&B);
    printf("%lld\n",solve_fast2(A,B));
  }
  
  return 0;
}

Compilation message

gauss.cpp: In function 'void init()':
gauss.cpp:211:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&K);
                 ^
gauss.cpp:212:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   FOR(i, 1, K + 1) scanf("%d",&f[i]);
                                     ^
gauss.cpp:213:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&L);
                 ^
gauss.cpp:215:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   REP(i, L) scanf("%d",&lens[i]);
                                 ^
gauss.cpp:218:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&M);
                 ^
gauss.cpp:221:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&x,&cost);
                            ^
gauss.cpp: In function 'int main()':
gauss.cpp:268:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&q);
                 ^
gauss.cpp:271:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&A,&B);
                         ^

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 139176 KB Output is correct
2 Correct 533 ms 139176 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 516 ms 139176 KB Output is correct
2 Correct 506 ms 139176 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 489 ms 139176 KB Output is correct
2 Correct 496 ms 139176 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 139176 KB Output is correct
2 Correct 499 ms 139176 KB Output is correct

Subtask #5
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 139176 KB Output is correct
2 Correct 836 ms 139176 KB Output is correct

Subtask #6
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 139176 KB Output is correct
2 Correct 893 ms 139176 KB Output is correct

Subtask #7
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 139176 KB Output is correct
2 Correct 1326 ms 139176 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1018 ms 139176 KB Output is correct
2 Correct 609 ms 139176 KB Output is correct

Subtask #9
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1223 ms 139176 KB Output is correct
2 Correct 826 ms 139176 KB Output is correct

Subtask #10
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1116 ms 139176 KB Output is correct
2 Correct 779 ms 139176 KB Output is correct