QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#33248#1177. BookfaceKuriyamaMiraiAC ✓165ms7224kbC++1411.1kb2022-05-30 19:24:242022-05-30 19:24:24

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-30 19:24:24]
  • 评测
  • 测评结果：AC
  • 用时：165ms
  • 内存：7224kb
查看
  • [2022-05-30 19:24:24]
  • 提交

answer

/**
 * @file 1177. Bookface.cpp
 * @author Kuriyama Mirai ([email protected])
 * @brief 
 * @date 2022-05-30
 * 
 * @copyright Copyright (c) 2022
 * 
 */
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cmath>
#include <unistd.h>
#include <queue>
#include <algorithm>

namespace mirai {
#define MIRAI_INPUT_BUFFER
#define MIRAI_INPUT_BUFFER_SIZE (1L << 16)
#define MIRAI_USE_ARG_LIST

#define ll long long
#define u unsigned
void flush_input(); ll sscan(); void sread(bool&); void sread(int&); void sread(u&); 
void sread(short&); void sread(long&); void sread(ll&); void sread(u short&); void sread(u long&); void sread(u ll&); 
void sread(char&); void sread(char*); void sread(float&); void sread(double&); void sread(long double&); 
template <typename type> void sread(type&); template <typename type, typename... Args> void sread(type&, Args&...); 
u ll scan(); void read(bool&); void read(int&); void read(short&); void read(long&); void read(ll&); void read(u int&); 
void read(u short&); void read(u long&); void read(u ll&); void read(char&); void read(char*); void read(float&);
void read(double&); void read(long double&); template <typename type> void read(type&);
template <typename type, typename... Args> void read(type&, Args&...); char readch(); char readc(); void readstr(char*);
float readf(); double readdf(); long double readlf();
#undef u
#undef ll
} // namespace mirai

#define MIRAI_TESTNO "1177-1"

namespace mirai {

using ll = long long;
std::priority_queue<ll> que;
ll a[2100000];

int main(int argc, char** argv) {
  int t = scan();
  while (t--) {
    while (!que.empty()) {
      que.pop();
    }
    ll n, d;
    read(n, d);
    for (int i = 1; i <= n; ++i) {
      a[i] = scan();
    }
    std::sort(a + 1, a + n + 1);
    ll tot = 0;
    for (int i = 1; i <= n; ++i) {
      ll x = a[i] - i * d;
      if (x < -d) {
        tot += -d - x;
        x = -d;
      }
      que.push(x);
      if (x < que.top()) {
        tot += que.top() - x;
        que.pop();
        que.push(x);
      }
    }
    std::printf("%lld\n", tot);
  }
  return 0;
}

} // namespace mirai

namespace mirai {

#if !defined(MIRAI_FORCE_USE_ARG_LIST) && defined(MIRAI_USE_ARG_LIST) && \
  __cplusplus < 201103L
#error MIRAI_USE_ARG_LIST needs C++11 to enable. \
use MIRAI_FORCE_USE_ARG_LIST if really need.
#endif
#ifdef MIRAI_FORCE_USE_ARG_LIST
#define MIRAI_USE_ARG_LIST
#endif

#if !defined(MIRAI_FORCE_ATTR_EXPECT) && defined(MIRAI_ATTR_EXPECT) && \
  __cplusplus < 202002L
#error MIRAI_ATTR_EXPECT needs C++20 to enable. \
use MIRAI_FORCE_ATTR_EXPECT if really need.
#undef MIRAI_ATTR_EXPECT
#endif
#ifdef MIRAI_FORCE_ATTR_EXPECT
#define MIRAI_ATTR_EXPECT
#endif

#ifdef MIRAI_ATTR_EXPECT
#define ift(x) [[likely]] if (x)
#define iff(x) [[unlikely]] if (x)
#define whilet(x) [[unlikely]] while (x)
#define whilef(x) [[likely]] while (x)
#elif defined(MIRAI_BUILTIN_EXPECT)
#define ift(x) if (__builtin_expect(!!(x), 1))
#define iff(x) if (__builtin_expect(!!(x), 0))
#define whilet(x) while (__builtin_expect(!!(x), 1))
#define whilef(x) while (__builtin_expect(!!(x), 0))
#else 
#define ift(x) if (x)
#define iff(x) if (x)
#define whilet(x) while (x)
#define whilef(x) while (x)
#endif

#ifndef MIRAI_INPUT_BUFFER_SIZE
#define MIRAI_INPUT_BUFFER_SIZE (1UL << 16)
#endif
#ifndef MIRAI_OUTPUT_BUFFER_SIZE
#define MIRAI_OUTPUT_BUFFER_SIZE (1UL << 16)
#endif

#ifdef MIRAI_INPUT_BUFFER
// let *input_buffer_end = '\0'.
char input_buffer[MIRAI_INPUT_BUFFER_SIZE + 1];
char *input_buffer_now = input_buffer;
char *input_buffer_end = input_buffer + MIRAI_INPUT_BUFFER_SIZE;

void flush_input(void) {
  #ifdef MIRAI_USE_READ_FUNC
  std::size_t ret = ::read(0, input_buffer, MIRAI_INPUT_BUFFER_SIZE);
  #else
  std::size_t ret = std::fread(input_buffer, sizeof(input_buffer[0]), 
    MIRAI_INPUT_BUFFER_SIZE, stdin);
  #endif
  iff(ret < MIRAI_INPUT_BUFFER_SIZE) {
    input_buffer[ret] = '\0';
  }
  input_buffer_now = input_buffer;
  return;
}
#else
void flush_input(void) {}
#endif

#ifndef MIRAI_INPUT_BUFFER
#define readchar() (std::getchar())
#else
char readchar(void) {
  iff(input_buffer_now == input_buffer_end) {
    flush_input();
  }
  return *(input_buffer_now++);
}
#endif

#ifdef MIRAI_USE_ISDIGIT
#define digit(x) (std::isdigit(x))
#else
#define digit(x) ((x) >= '0' && (x) <= '9')
#endif

void readstr(char*);

long long sscan(void) {
  char ch = readchar();
  whilet(!digit(ch) && ch != '-') {
    ch = readchar();
  }
  unsigned long long ret = 0;
  bool flag = false;
  iff(ch != '-') {
    ret = ch - '0';
  } else {
    flag = true;
  }
  ch = readchar();
  whilet(digit(ch)) {
    ret = ret * 10 + ch - '0';
    ch = readchar();
  }
  iff(flag) {
    return -ret;
  } else {
    return ret;
  }
}

void sread(bool& u) { u = sscan(); }
void sread(int& u) { u = sscan(); }
void sread(short& u) { u = sscan(); }
void sread(long& u) { u = sscan(); }
void sread(long long& u) { u = sscan(); }
void sread(unsigned int& u) { u = sscan(); }
void sread(unsigned short& u) { u = sscan(); }
void sread(unsigned long& u) { u = sscan(); }
void sread(unsigned long long& u) { u = sscan(); }

void sread(char& u) {
  u = readchar();
  return;
}
void sread(char* str) {
  readstr(str);
  return;
}

void sread(float& u) { u = readf(); }
void sread(double& u) { u = readdf(); }
void sread(long double& u) { u = readlf(); }

#ifdef MIRAI_USE_ARG_LIST
// Very SLOW.
template <typename type, typename... Args>
void sread(type &u, Args&... args) {
  sread(u);
  sread(args...);
  return;
}
#endif

// ignores character '-'.
unsigned long long scan(void) {
  char ch = readchar();
  whilet(!digit(ch)) {
    ch = readchar();
  }
  unsigned long long ret = ch - '0';
  ch = readchar();
  whilet(digit(ch)) {
    ret = ret * 10 + ch - '0';
    ch = readchar();
  }
  return ret;
}

void read(bool& u) { u = scan(); }
void read(int& u) { u = scan(); }
void read(short& u) { u = scan(); }
void read(long& u) { u = scan(); }
void read(long long& u) { u = scan(); }
void read(unsigned int& u) { u = scan(); }
void read(unsigned short& u) { u = scan(); }
void read(unsigned long& u) { u = scan(); }
void read(unsigned long long& u) { u = scan(); }

void read(char& u) {
  u = readchar();
}
void read(char* str) {
  readstr(str);
  return;
}

void read(float& u) { u = readf(); }
void read(double& u) { u = readdf(); }
void read(long double& u) { u = readlf(); }

#ifdef MIRAI_USE_ARG_LIST
// Very SLOW.
template <typename type, typename... Args>
void read(type &u, Args&... args) {
  read(u);
  read(args...);
  return;
}
#endif

char readch(void) {
  char ch;
  ch = readchar();
  return ch;
}
char readc(void) {
  char ch;
  ch = readchar();
  whilet(std::isblank(ch)) {
    ch = readchar();
  }
  return ch;
}

void readstr(char* str) {
  *str = readchar();
  whilef(std::isblank(*str)) {
    *str = readchar();
    str++;
  }
  *str = '\0';
  return;
}

float readf(void) {
  float x = 0;
  char ch = readchar();
  whilet(!digit(ch) && ch != '-') {
    ch = readchar();
  }
  bool flag = false;
  iff(ch == '-') {
    flag = true;
  } else iff(ch != '+' && ch != '.') {
    x = ch - '0';
  }
  ch = readchar();
  whilet(digit(ch)) {
    x = x * 10 + ch - '0';
    ch = readchar();
  }
  ift(ch == '.') {
    float tmp = 0;
    tmp = 0.1;
    ch = readchar();
    whilet(digit(ch)) {
      x += tmp * (ch - '0');
      tmp = tmp * 0.1;
      ch = readchar();
    }
  }
  ift(ch == 'e' || ch == 'E') {
    unsigned int y = 0, cnt = 6;
    ch = readchar();
    bool flag2 = false;
    iff(ch == '-') {
      flag2 = true;
    } else ift(digit(ch)) {
      y = ch - '0';
      cnt--;
    }
    ch = readchar();
    whilet(digit(ch) && cnt) {
      y = y * 10 + (ch - '0');
      cnt--;
      ch = readchar();
    }
    if (digit(ch) && cnt == 0) {
      while (digit(ch)) {
        ch = readchar();
      }
    }
    if (flag2) {
      x = x * std::pow(10.F, -1.F * y);
    } else {
      x = x * std::pow<float, float>(10, y);
    }
  }
  iff(flag) {
    return -x;
  } else {
    return x;
  }
}
double readdf(void) {
  double x = 0;
  char ch = readchar();
  whilet(!digit(ch) && ch != '-') {
    ch = readchar();
  }
  bool flag = false;
  iff(ch == '-') {
    flag = true;
  } else iff(ch != '+' && ch != '.') {
    x = ch - '0';
  }
  ch = readchar();
  whilet(digit(ch)) {
    x = x * 10 + ch - '0';
    ch = readchar();
  }
  ift(ch == '.') {
    double tmp = 0;
    tmp = 0.1;
    ch = readchar();
    whilet(digit(ch)) {
      x += tmp * (ch - '0');
      tmp = tmp * 0.1;
      ch = readchar();
    }
  }
  ift(ch == 'e' || ch == 'E') {
    unsigned int y = 0, cnt = 6;
    ch = readchar();
    bool flag2 = false;
    iff(ch == '-') {
      flag2 = true;
    } else ift(digit(ch)) {
      y = ch - '0';
      cnt--;
    }
    ch = readchar();
    whilet(digit(ch) && cnt) {
      y = y * 10 + (ch - '0');
      cnt--;
      ch = readchar();
    }
    if (digit(ch) && cnt == 0) {
      while (digit(ch)) {
        ch = readchar();
      }
    }
    if (flag2) {
      x = x * std::pow(10.F, -1.F * y);
    } else {
      x = x * std::pow<double, double>(10, y);
    }
  }
  iff(flag) {
    return -x;
  } else {
    return x;
  }
}
long double readlf(void) {
  long double x = 0;
  char ch = readchar();
  whilet(!digit(ch) && ch != '-') {
    ch = readchar();
  }
  bool flag = false;
  iff(ch == '-') {
    flag = true;
  } else iff(ch != '+' && ch != '.') {
    x = ch - '0';
  }
  ch = readchar();
  whilet(digit(ch)) {
    x = x * 10 + ch - '0';
    ch = readchar();
  }
  ift(ch == '.') {
    long double tmp = 0;
    tmp = 0.1;
    ch = readchar();
    whilet(digit(ch)) {
      x += tmp * (ch - '0');
      tmp = tmp * 0.1;
      ch = readchar();
    }
  }
  ift(ch == 'e' || ch == 'E') {
    unsigned int y = 0, cnt = 6;
    ch = readchar();
    bool flag2 = false;
    iff(ch == '-') {
      flag2 = true;
    } else ift(digit(ch)) {
      y = ch - '0';
      cnt--;
    }
    ch = readchar();
    whilet(digit(ch) && cnt) {
      y = y * 10 + (ch - '0');
      cnt--;
      ch = readchar();
    }
    if (digit(ch) && cnt == 0) {
      while (digit(ch)) {
        ch = readchar();
      }
    }
    if (flag2) {
      x = x * std::pow(10.L, -1.L * y);
    } else {
      x = x * std::pow<long double, long double>(10, y);
    }
  }
  iff(flag) {
    return -x;
  } else {
    return x;
  }
}

#undef ift
#undef iff
#undef whilet
#undef whilef
#undef digit
#undef readchar

} // namespace mirai

int main(int argc, char** argv) {
  #ifdef MIRAI_LOCAL
  std::freopen(__FILE__ R"(\..\tests\)" MIRAI_TESTNO ".in", "r", stdin);
  std::freopen(__FILE__ R"(\..\tests\)" MIRAI_TESTNO ".out", "w", stdout);
  #endif
  #ifdef MIRAI_INPUT_BUFFER
  mirai::flush_input();
  #endif
  int ret = mirai::main(argc, argv);
  #ifdef MIRAI_LOCAL 
  std::fclose(stdin);
  std::fclose(stdout);
  #endif
  return ret;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3040kb

input:

2
4 1
0 0 0 0
4 10
1 100 5 10

output:

6
16

result:

ok 2 number(s): "6 16"

Test #2:

score: 0
Accepted
time: 28ms
memory: 3020kb

input:

98280
7 8
299 294 297 292 293 290 289
7 7
11 7 9 2 6 4 0
6 2
295 296 288 292 289 290
8 7
294 298 295 290 292 293 297 291
8 8
292 299 290 293 296 288 298 295
8 4
290 288 298 295 299 289 296 292
4 4
10 2 0 7
4 2
291 298 297 299
5 6
296 288 298 299 293
5 10
290 294 295 293 296
8 11
0 11 4 8 10 5 2 9
4 ...

output:

77
108
4
94
103
35
5
2
20
52
259
35
50
100
66
21
47
64
92
91
104
45
13
61
31
12
62
4
0
35
12
72
79
5
135
100
149
58
126
193
8
104
0
41
18
21
88
0
10
69
2
0
87
2
8
82
51
198
1
2
145
21
102
7
0
106
0
111
41
18
39
129
2
99
20
19
23
18
12
7
29
52
24
0
49
91
74
14
37
152
17
54
60
88
14
0
34
14
8
41
25
20...

result:

ok 98280 numbers

Test #3:

score: 0
Accepted
time: 134ms
memory: 3092kb

input:

669
1703 762924
873022128 300066207 1206419913 1269742605 1079774532 85684564 320665155 546490659 547253583 55167604 828772536 306169599 950840376 790626336 146718484 475538727 1200316521 595317794 1025606928 794440956 243609831 1233122253 566326683 808173588 569378379 989749500 1294919097 716622708...

output:

3253
458301850
79
80535
235992546
48759003
306315842
128083532
332544825
14768472
3771
385408117
125880821
251912220
378698670
22018229
2248
10203802
247102873
2556
3659
182576709
387349688
254103271
3989
78877516
276786211
132052865
318642737
2674
3340
180128422
521438360
349874364
491202128
299606...

result:

ok 669 numbers

Test #4:

score: 0
Accepted
time: 165ms
memory: 7224kb

input:

5
200000 733779
5361989373 113163663523 99233602998 108403639154 58100887401 120013490484 71790268408 126920552205 111792230572 115622556950 38382044346 137127418089 117789406336 93700909340 140037585603 122991899442 97647906580 114932070911 64487699812 12479645668 97811539297 59197887004 3165035581...

output:

5227485
16167521795
10000000000
34035608352
36804

result:

ok 5 number(s): "5227485 16167521795 10000000000 34035608352 36804"
English 繁體中文 简体中文

Server Time: 2025-01-20 12:13:04 | OpenSource Project