QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #751348 | #9738. Make It Divisible | yeVegeTable | Compile Error | / | / | C++20 | 5.9kb | 2024-11-15 18:15:51 | 2024-11-15 18:15:52 |
Judging History
你现在查看的是最新测评结果
- [2024-11-27 18:44:44]
- hack成功，自动添加数据
- (/hack/1263)
- [2024-11-15 18:15:52]
- 评测
- 测评结果：Compile Error
- 用时：0ms
- 内存：0kb
- [2024-11-15 18:15:51]
- 提交
answer
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<ll, ll> P;
#define x first
#define y second
#define int long long
const int mod = 1e9 + 7;
const int pp = 998244353;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
ll ksm(ll a, ll b, ll p) {
ll ans = 1;
a %= p;
while(b) {
if(b & 1) ans = (ans * a) % p;
b >>= 1;
a = (a * a) % p;
}
return ans % p;
}
std::mt19937 rng; // 随机数生成器
int rand(int l, int r) {
std::uniform_int_distribution<int> distribution(l, r);
return distribution(rng);
}
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 2);
int idx = -1;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(i > 1 && a[i] != a[i - 1]) {
idx = i;
}
}
if(n == 1 || idx == -1) {
cout << k << " " << k * (k + 1) / 2 << endl;
return ;
}
vector<int> s(1);
vector<int> L(n + 1, -1);
for(int i = 1; i <= n; i++) {
while(s.size() && a[s.back()] <= a[i]) {
s.pop_back();
}
if(s.size()) {
L[i] = s.back();
}
s.emplace_back(i);
}
s = vector<int>(1, n + 1);
vector<int> R(n + 1, -1);
for(int i = n; i > 0; i--) {
while(s.size() && a[s.back()] <= a[i]) {
s.pop_back();
}
if(s.size()) {
R[i] = s.back();
}
s.emplace_back(i);
}
assert(R[1] != -1);
int A = a[1], B = a[R[1]], C = B - A;
// (B + x) = k * (A + x) -> B = k*A + (k-1)*x -> B - A = (A + x) * (k - 1)
set<int> st;
for(int i = 1; i * i <= C; i++) {
if(C % i) continue;
int f1 = i, f2 = C / i;
for(auto & j : {f1, f2}) {
if(j > A && j - A <= k) {
st.emplace(j - A);
}
}
}
int m = st.size();
vector<int> v;
for(auto & x : st) {
v.emplace_back(x);
}
vector<int> vis(m);
for(int i = 1; i <= n; i++) {
for(auto & j : {L[i], R[i]}) {
if(j == -1) continue;
for(int u = 0; u < m; u++) {
if(vis[u]) continue;
if((a[j] + v[u]) % (a[i] + v[u])) {
vis[u] = 1;
}
}
}
}
int cnt = 0, sum = 0;
for(int i = 0; i < m; i++) {
if(vis[i]) continue;
cnt ++ ;
sum += v[i];
}
cout << cnt << " " << sum << endl;
}
/*
*/
signed main () {
// init(minp, primes, m); // primes
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// init();
int _ = 1;
cin >> _;
while(_ -- ) {
solve();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<ll, ll> P;
#define x first
#define y second
#define int long long
const int mod = 1e9 + 7;
const int pp = 998244353;
const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
ll ksm(ll a, ll b, ll p) {
ll ans = 1;
a %= p;
while(b) {
if(b & 1) ans = (ans * a) % p;
b >>= 1;
a = (a * a) % p;
}
return ans % p;
}
std::mt19937 rng; // 随机数生成器
int rand(int l, int r) {
std::uniform_int_distribution<int> distribution(l, r);
return distribution(rng);
}
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n + 2);
int idx = -1;
for(int i = 1; i <= n; i++) {
cin >> a[i];
if(i > 1 && a[i] != a[i - 1]) {
idx = i;
}
}
if(n == 1 || idx == -1) {
cout << k << " " << k * (k + 1) / 2 << endl;
return ;
}
vector<int> s(1);
vector<int> L(n + 1, -1);
for(int i = 1; i <= n; i++) {
while(s.size() && a[s.back()] <= a[i]) {
s.pop_back();
}
if(s.size()) {
L[i] = s.back();
}
s.emplace_back(i);
}
s = vector<int>(1, n + 1);
vector<int> R(n + 1, -1);
for(int i = n; i > 0; i--) {
while(s.size() && a[s.back()] <= a[i]) {
s.pop_back();
}
if(s.size()) {
R[i] = s.back();
}
s.emplace_back(i);
}
assert(R[1] != -1);
int A = a[1], B = a[R[1]], C = B - A;
// (B + x) = k * (A + x) -> B = k*A + (k-1)*x -> B - A = (A + x) * (k - 1)
set<int> st;
for(int i = 1; i * i <= C; i++) {
if(C % i) continue;
int f1 = i, f2 = C / i;
for(auto & j : {f1, f2}) {
if(j > A && j - A <= k) {
st.emplace(j - A);
}
}
}
int m = st.size();
vector<int> v;
for(auto & x : st) {
v.emplace_back(x);
}
vector<int> vis(m);
for(int i = 1; i <= n; i++) {
for(auto & j : {L[i], R[i]}) {
if(j == -1) continue;
for(int u = 0; u < m; u++) {
if(vis[u]) continue;
if((a[j] + v[u]) % (a[i] + v[u])) {
vis[u] = 1;
}
}
}
}
int cnt = 0, sum = 0;
for(int i = 0; i < m; i++) {
if(vis[i]) continue;
cnt ++ ;
sum += v[i];
}
cout << cnt << " " << sum << endl;
}
/*
*/
signed main () {
// init(minp, primes, m); // primes
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
// init();
int _ = 1;
cin >> _;
while(_ -- ) {
solve();
}
return 0;
}
详细
answer.code:130:2: error: stray ‘#’ in program
130 | }#include <bits/stdc++.h>
| ^
answer.code:130:12: error: ‘bits’ was not declared in this scope
130 | }#include <bits/stdc++.h>
| ^~~~
answer.code:130:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
130 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:130:12: error: ‘bits’ was not declared in this scope
130 | }#include <bits/stdc++.h>
| ^~~~
answer.code:130:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
130 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:130:12: error: ‘bits’ was not declared in this scope
130 | }#include <bits/stdc++.h>
| ^~~~
answer.code:130:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
130 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:130:12: error: ‘bits’ was not declared in this scope
130 | }#include <bits/stdc++.h>
| ^~~~
answer.code:130:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
130 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:130:12: error: ‘bits’ was not declared in this scope
130 | }#include <bits/stdc++.h>
| ^~~~
answer.code:130:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
130 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:130:12: error: ‘bits’ was not declared in this scope
130 | }#include <bits/stdc++.h>
| ^~~~
answer.code:130:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
130 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:130:12: error: ‘bits’ was not declared in this scope
130 | }#include <bits/stdc++.h>
| ^~~~
answer.code:130:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
130 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:130:12: error: ‘bits’ was not declared in this scope
130 | }#include <bits/stdc++.h>
| ^~~~
answer.code:130:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
130 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:130:12: error: ‘bits’ was not declared in this scope
130 | }#include <bits/stdc++.h>
| ^~~~
answer.code:130:17: error: ‘stdc’ was not declared in this scope; did you mean ‘std’?
130 | }#include <bits/stdc++.h>
| ^~~~
| std
answer.code:130:3: error: ‘include’ does not name a type
130 | }#include <bits/stdc++.h>
| ^~~~~~~
answer.code:141:11: error: redefinition of ‘const long long int mod’
141 | const int mod = 1e9 + 7;
| ^~~
answer.code:12:11: note: ‘const long long int mod’ previously defined here
12 | const int mod = 1e9 + 7;
| ^~~
answer.code:142:11: error: redefinition of ‘const long long int pp’
142 | const int pp = 998244353;
| ^~
answer.code:13:11: note: ‘const long long int pp’ previously defined here
13 | const int pp = 998244353;
| ^~
answer.code:144:11: error: redefinition of ‘const long long int dx [8]’
144 | const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
| ^~
answer.code:15:11: note: ‘const long long int dx [8]’ previously defined here
15 | const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
| ^~
answer.code:144:48: error: redefinition of ‘const long long int dy [8]’
144 | const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
| ^~
answer.code:15:48: note: ‘const long long int dy [8]’ previously defined here
15 | const int dx[8] = {-1, 0, 1, 0, -1, -1, 1, 1}, dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
| ^~
answer.code:145:11: error: redefinition of ‘const long long int ddx [8]’
145 | const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
| ^~~
answer.code:16:11: note: ‘const long long int ddx [8]’ previously defined here
16 | const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
| ^~~
answer.code:145:50: error: redefinition of ‘const long long int ddy [8]’
145 | const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, -2, 1, -1, 2, -2, 1, -1};
| ^~~
answer.code:16:50: note: ‘const long long int ddy [8]’ previously defined here
16 | const int ddx[8] = {1, 1, 2, 2, -1, -1, -2, -2}, ddy[8] = {2, ...