QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#87335#5674. Sum of Remainderssinbad#AC ✓2ms3476kbC++4.2kb2023-03-12 16:27:052023-03-12 16:27:07

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-12 16:27:07]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:3476kb
  • [2023-03-12 16:27:05]
  • 提交

answer

#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const multiset<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
  return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}

using int64 = long long;
using int128 = __int128_t;
using ii = pair<int, int>;
#define SZ(x) (int)((x).size())
template <typename T> static constexpr T inf = numeric_limits<T>::max() / 2;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
mt19937_64 mrand(random_device{}());
int64 rnd(int64 x) { return mrand() % x; }
constexpr inline int lg2(int64 x) { return x == 0 ? -1 : sizeof(int64) * 8 - 1 - __builtin_clzll(x); }
constexpr inline int p2ceil(int64 x) { return 1 << (lg2(x - 1) + 1); }
template <class T> void out(const vector<T>& a) { for (int i = 0; i < SZ(a); ++i) cout << a[i] << " \n"[i + 1 == SZ(a)]; }
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> void dedup(vector<T>& v) { sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); }
inline void add_mod(int& x, int y) { x += y; if (x >= MOD) x -= MOD; }
inline void sub_mod(int& x, int y) { x += MOD - y; if (x >= MOD) x -= MOD; }
inline int mod(int x) { return x >= MOD ? x - MOD : x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

int main() {
  int n;
  cin >> n;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; ++i) cin >> a[i];
  int m = a[1];
  vector<int> ret;
  for (int i = 2; i <= n; ++i) {
    int val = a[i - 1] + m;
    for (auto& x : ret) {
      if (i % x == 0) val -= x;
    }
    if (a[i] != val) {
      val = (val - a[i]) / i;
      while (val--) ret.push_back(i);
    }
    // trace(i, ret);
  }

  cout << SZ(ret) << " ";
  out(ret);

  return 0;
}

詳細信息

Test #1:

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

input:

16
4 6 10 12 6 8 12 14 18 10
3 5 9 11 5 7

output:

4 2 5 5 11

result:

ok single line: '4 2 5 5 11'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3476kb

input:

20
3 6 6 9 12 6 2 5 5 8
11 5 8 4 4 7 10 4 7 10

output:

3 3 6 7

result:

ok single line: '3 3 6 7'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3392kb

input:

40
7 14 21 28 35 42 42 49 56 63
70 65 59 45 37 44 51 58 65 72
72 79 86 57 39 33 40 26 33 25
32 39 46 53 53 48 55 62 56 63

output:

7 7 12 13 14 15 24 25

result:

ok single line: '7 7 12 13 14 15 24 25'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3372kb

input:

60
7 14 21 28 35 42 49 56 63 70
77 72 79 86 93 100 90 97 85 92
99 106 113 108 115 122 102 109 116 123
99 106 113 103 110 105 112 100 107 114
121 86 93 56 63 70 77 72 79 86
76 83 90 70 77 84 72 79 86 81

output:

7 12 17 19 27 31 42 44

result:

ok single line: '7 12 17 19 27 31 42 44'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

20
1 2 3 4 5 6 7 8 0 1
2 3 4 5 6 7 8 0 1 2

output:

1 9

result:

ok single line: '1 9'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3368kb

input:

30
2 4 6 8 10 12 14 16 18 20
11 13 2 4 6 8 10 12 14 16
18 9 11 13 15 4 6 8 10 12

output:

2 11 13

result:

ok single line: '2 11 13'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3440kb

input:

40
9 18 24 33 42 42 51 60 66 65
74 74 70 79 70 47 56 56 46 45
51 60 69 45 54 50 56 65 74 49
58 35 41 50 59 59 68 58 51 50

output:

9 3 6 10 13 15 16 16 19 24

result:

ok single line: '9 3 6 10 13 15 16 16 19 24'

Test #8:

score: 0
Accepted
time: 2ms
memory: 3372kb

input:

60
7 14 21 28 35 42 49 48 55 62
69 76 83 76 83 82 89 96 103 110
117 124 131 130 137 144 151 144 151 158
165 164 171 144 151 158 165 172 179 138
145 138 145 108 70 77 84 83 90 47
54 61 68 75 82 67 74 81 88 95

output:

7 8 14 34 40 44 45 50

result:

ok single line: '7 8 14 34 40 44 45 50'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3372kb

input:

70
3 6 9 12 15 18 21 24 27 30
33 36 39 42 45 48 51 54 57 60
63 66 69 72 75 78 81 84 87 60
63 66 69 72 75 78 81 84 87 90
93 96 99 102 60 63 66 69 72 75
78 81 84 33 36 39 42 45 48 21
24 27 30 33 36 39 42 45 48 51

output:

3 30 45 54

result:

ok single line: '3 30 45 54'

Test #10:

score: 0
Accepted
time: 2ms
memory: 3420kb

input:

30
5 10 15 16 21 20 25 26 31 26
31 26 31 36 41 42 30 29 15 6
11 16 21 16 21 26 31 32 37 26

output:

5 4 6 10 17 19

result:

ok single line: '5 4 6 10 17 19'