# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
386728 | 2021-04-07T08:44:40 Z | vanic | Gift (IZhO18_nicegift) | C++14 | 2000 ms | 129612 KB |
#include <cstdio> #include <cmath> #include <algorithm> #include <set> #include <bitset> using namespace std; typedef long long ll; const int maxn=1e6+5; ll a[maxn]; ll sum; pair < ll, int > v[maxn*4]; set < int > cur; void scan(ll &a){ a=0; char c=getchar(); while(c>='0' && c<='9'){ a*=10; a+=c-'0'; c=getchar(); } } int main(){ int n, k; scanf("%d%d", &n, &k); for(int i=0; i<n; i++){ scanf("%lld", a+i); sum+=a[i]; } if(sum%k){ printf("-1\n"); return 0; } sum/=k; for(int i=0; i<n; i++){ if(a[i]>sum){ printf("-1\n"); return 0; } } int pos=0; int iduc; int br=0; for(int i=0; i<n; i++){ iduc=pos+a[i]; if(iduc>sum){ v[br]={pos, i+1}; br++; v[br]={sum, -i-1}; br++; iduc-=sum; pos=0; } v[br]={pos, i+1}; br++; v[br]={iduc, -i-1}; br++; if(iduc==sum){ iduc=0; } pos=iduc; } sort(v, v+br); int sol=0; for(int i=0; i<br-1; i++){ if(v[i].first!=v[i+1].first){ sol++; } } printf("%d\n", sol); for(int i=0; i<br-1; i++){ if(v[i].second>0){ cur.insert(v[i].second); } else{ cur.erase(-v[i].second); } if(v[i].first==v[i+1].first){ continue; } printf("%lld ", v[i+1].first-v[i].first); for(set < int >::iterator it=cur.begin(); it!=cur.end(); it++){ printf("%d ", *it); } printf("\n"); } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | n=4 |
2 | Correct | 1 ms | 364 KB | n=3 |
3 | Correct | 1 ms | 364 KB | n=3 |
4 | Correct | 1 ms | 364 KB | n=4 |
5 | Correct | 1 ms | 364 KB | n=4 |
6 | Correct | 1 ms | 364 KB | n=2 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | n=4 |
2 | Correct | 1 ms | 364 KB | n=3 |
3 | Correct | 1 ms | 364 KB | n=3 |
4 | Correct | 1 ms | 364 KB | n=4 |
5 | Correct | 1 ms | 364 KB | n=4 |
6 | Correct | 1 ms | 364 KB | n=2 |
7 | Correct | 1 ms | 364 KB | n=5 |
8 | Correct | 1 ms | 364 KB | n=8 |
9 | Correct | 1 ms | 364 KB | n=14 |
10 | Correct | 1 ms | 364 KB | n=11 |
11 | Correct | 32 ms | 2924 KB | n=50000 |
12 | Correct | 32 ms | 2924 KB | n=50000 |
13 | Correct | 1 ms | 364 KB | n=10 |
14 | Correct | 1 ms | 364 KB | n=685 |
15 | Correct | 1 ms | 364 KB | n=623 |
16 | Correct | 2 ms | 364 KB | n=973 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | n=4 |
2 | Correct | 1 ms | 364 KB | n=3 |
3 | Correct | 1 ms | 364 KB | n=3 |
4 | Correct | 1 ms | 364 KB | n=4 |
5 | Correct | 1 ms | 364 KB | n=4 |
6 | Correct | 1 ms | 364 KB | n=2 |
7 | Correct | 1 ms | 364 KB | n=5 |
8 | Correct | 1 ms | 364 KB | n=8 |
9 | Correct | 1 ms | 364 KB | n=14 |
10 | Correct | 1 ms | 364 KB | n=11 |
11 | Correct | 32 ms | 2924 KB | n=50000 |
12 | Correct | 32 ms | 2924 KB | n=50000 |
13 | Correct | 1 ms | 364 KB | n=10 |
14 | Correct | 1 ms | 364 KB | n=685 |
15 | Correct | 1 ms | 364 KB | n=623 |
16 | Correct | 2 ms | 364 KB | n=973 |
17 | Correct | 2 ms | 364 KB | n=989 |
18 | Correct | 2 ms | 364 KB | n=563 |
19 | Correct | 3 ms | 364 KB | n=592 |
20 | Correct | 3 ms | 364 KB | n=938 |
21 | Correct | 2 ms | 364 KB | n=747 |
22 | Correct | 3 ms | 364 KB | n=991 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2097 ms | 129612 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 364 KB | n=4 |
2 | Correct | 1 ms | 364 KB | n=3 |
3 | Correct | 1 ms | 364 KB | n=3 |
4 | Correct | 1 ms | 364 KB | n=4 |
5 | Correct | 1 ms | 364 KB | n=4 |
6 | Correct | 1 ms | 364 KB | n=2 |
7 | Correct | 1 ms | 364 KB | n=5 |
8 | Correct | 1 ms | 364 KB | n=8 |
9 | Correct | 1 ms | 364 KB | n=14 |
10 | Correct | 1 ms | 364 KB | n=11 |
11 | Correct | 32 ms | 2924 KB | n=50000 |
12 | Correct | 32 ms | 2924 KB | n=50000 |
13 | Correct | 1 ms | 364 KB | n=10 |
14 | Correct | 1 ms | 364 KB | n=685 |
15 | Correct | 1 ms | 364 KB | n=623 |
16 | Correct | 2 ms | 364 KB | n=973 |
17 | Correct | 2 ms | 364 KB | n=989 |
18 | Correct | 2 ms | 364 KB | n=563 |
19 | Correct | 3 ms | 364 KB | n=592 |
20 | Correct | 3 ms | 364 KB | n=938 |
21 | Correct | 2 ms | 364 KB | n=747 |
22 | Correct | 3 ms | 364 KB | n=991 |
23 | Execution timed out | 2097 ms | 129612 KB | Time limit exceeded |
24 | Halted | 0 ms | 0 KB | - |