QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#841440 | #8708. Portal | zhassyn# | 0 | 9ms | 5840kb | C++20 | 2.1kb | 2025-01-03 19:03:31 | 2025-01-03 19:03:32 |
Judging History
answer
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 1e5 + 100, M = 316 + 10, len = 315, inf = 1e18;
const ll mod = 1e9 + 7;
ll um(ll a, ll b){
return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
return ((1LL * a - b) % mod + mod) % mod;
}
ll n, x[N], d[N], dp[N];
void subtask2(){
ll ans = 0;
dp[1] = 1;
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= x[i]; j++){
if(i + d[i] * j > n || d[i] == 0) break;
dp[i + d[i] * j] += dp[i];
dp[i + d[i] * j] %= mod;
}
//cout << dp[i] << endl;
ans += dp[i];
ans %= mod;
}
cout << ans;
}
void subtask3(){
ll sum = 1, ans = 1;
set <pll> st;
dp[1] = 1;
st.insert({x[1] + 1, 1});
for(ll i = 2; i <= n; i++){
while((ll)st.size() != 0){
ll v = st.begin()->F;
if(v < i){
//cout << st.begin()->F << " "<< st.begin()->S << " INFO\n";
sum = subr(sum, dp[st.begin()->S]);
st.erase(st.begin());
} else break;
}
ans += sum;
ans %= mod;
dp[i] = sum;
st.insert({x[i] + i, i});
//cout << i << " "<< sum << endl;
sum = um(sum, 2LL);
}
cout << ans;
}
ll mas[M][M];
void subtask4(){
ll ans = 0;
dp[1] = 1;
for(ll i = 1; i <= n; i++){
for(ll j = 1; j <= 316; j++){
dp[i] += mas[j][i % j];
dp[i] %= mod;
}
ans += dp[i];
ans %= mod;
if(d[i] == 0) continue;
if(d[i] <= 316){
mas[d[i]][i % d[i]] += dp[i];
mas[d[i]][i % d[i]] %= mod;
} else{
for(ll j = 1; j <= x[i]; j++){
if(j * d[i] + i > n) break;
dp[j * d[i] + i] += dp[i];
dp[j * d[i] + i] %= mod;
}
}
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
bool c3 = true, c4 = true;
for(ll i = 1; i <= n; i++){
cin >> d[i] >> x[i];
if(d[i] != 1) c3 = false;
if(x[i] != 1e9) c4 = false;
}
if(n <= 10000){
subtask2();
return 0;
}
if(c3){
subtask3();
return 0;
}
if(c4){
subtask4();
return 0;
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 5660kb
input:
1 1 -1
output:
1
result:
wrong answer 1st lines differ - expected: '-1', found: '1'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Wrong Answer
Test #40:
score: 0
Wrong Answer
time: 9ms
memory: 5840kb
input:
99840 -359536 735499 -710626 400619 -468266 -282389 -192706 43659 204034 -543669 -100576 -749013 -118006 -283125 -341276 405771 560934 835595 -923936 506603 239724 956299 -680746 -737237 286204 982795 -847576 -282389 -949666 986475 996684 -429589 672984 -133717 140954 696491 -879116 -442837 985064 7...
output:
result:
wrong answer 1st lines differ - expected: '610880', found: ''
Subtask #4:
score: 0
Wrong Answer
Test #59:
score: 29
Accepted
time: 0ms
memory: 3592kb
input:
5 0 0 1 0 -1 0 0 1 0 -1
output:
1
result:
ok single line: '1'
Test #60:
score: 0
Wrong Answer
time: 1ms
memory: 3880kb
input:
100 -30 -13 -22 -19 32 9 -18 -11 50 19 16 5 -50 -17 -46 -21 10 -1 -56 -19 2 -11 -24 -15 -4 -11 -8 -11 4 7 -8 -5 34 9 18 7 20 1 -12 -11 -30 -23 -42 -13 -24 -3 16 11 -16 -7 -24 -21 2 -9 28 11 6 -9 -22 -11 4 -7 28 7 -36 -15 -20 -21 4 11 -8 5 20 5 30 21 58 19 4 -1 -46 -19 -6 3 2 11 46 15 18 -1 -24 -7 -2...
output:
1
result:
wrong answer 1st lines differ - expected: '4', found: '1'
Subtask #5:
score: 0
Skipped
Dependency #2:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%