QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#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;
}
Details
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, ...