Task: | Tikut |
Sender: | Kemm1706 |
Submission time: | 2024-11-07 20:54:26 +0200 |
Language: | C++ (C++11) |
Status: | READY |
Result: | 27 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 7 |
#2 | ACCEPTED | 8 |
#3 | ACCEPTED | 12 |
#4 | WRONG ANSWER | 0 |
#5 | WRONG ANSWER | 0 |
#6 | WRONG ANSWER | 0 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.00 s | 1, 3, 4, 5, 6 | details |
#2 | ACCEPTED | 0.00 s | 1, 4, 5, 6 | details |
#3 | ACCEPTED | 0.00 s | 1, 4, 5, 6 | details |
#4 | ACCEPTED | 0.00 s | 1, 4, 5, 6 | details |
#5 | ACCEPTED | 0.01 s | 2, 5, 6 | details |
#6 | ACCEPTED | 0.01 s | 2, 5, 6 | details |
#7 | ACCEPTED | 0.00 s | 3, 5, 6 | details |
#8 | ACCEPTED | 0.00 s | 3, 5, 6 | details |
#9 | ACCEPTED | 0.00 s | 3, 5, 6 | details |
#10 | ACCEPTED | 0.01 s | 3, 5, 6 | details |
#11 | ACCEPTED | 0.00 s | 3, 5, 6 | details |
#12 | WRONG ANSWER | 0.00 s | 4, 5, 6 | details |
#13 | WRONG ANSWER | 0.00 s | 4, 5, 6 | details |
#14 | WRONG ANSWER | 0.00 s | 4, 5, 6 | details |
#15 | WRONG ANSWER | 0.00 s | 4, 5, 6 | details |
#16 | WRONG ANSWER | 0.01 s | 5, 6 | details |
#17 | WRONG ANSWER | 0.01 s | 5, 6 | details |
#18 | WRONG ANSWER | 0.01 s | 5, 6 | details |
#19 | WRONG ANSWER | 0.01 s | 5, 6 | details |
#20 | WRONG ANSWER | 0.17 s | 6 | details |
#21 | WRONG ANSWER | 0.13 s | 6 | details |
#22 | WRONG ANSWER | 0.19 s | 6 | details |
Compiler report
input/code.cpp: In function 'void sub1(vl&, ll, ll)': input/code.cpp:48:26: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare] 48 | if (v.size() <= h) | ~~~~~~~~~^~~~ input/code.cpp: In function 'int main()': input/code.cpp:89:45: warning: unused variable 'mn' [-Wunused-variable] 89 | ll n, m, i, j, k, a, b, r, t, f = 0, c, mn, S = 0; | ^~ input/code.cpp:191:21: warning: 'b' may be used uninitialized in this function [-Wmaybe-uninitialized] 191 | cout << a - b << " "; | ^ input/code.cpp:191:21: warning: 'a' may be used uninitialized in this function [-Wmaybe-uninitialized]
Code
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef vector<ll> vl;typedef pair<ll,ll> pl;typedef vector <pl> vpl;#define fi first#define se second#define mp make_pair#define outp(a) for(auto x:a) cerr << x << " "; cerr << " <--\n";const ll inf = 1e18;ll cal(vl &x, vl &v){ll i, j, mn, mx, cmn, cmx, c;mn = inf;mx = -inf;for(i = v.size()-1, j = x.size() - 1; i >= 0; i--, j--){c = v[i] + 1;cmn = x[j] / c;if (cmn == 0) return inf;cmx = (x[j] + c - 1) / c;mn = min(mn, cmn);mx = max(mx, cmx);}for(; j >= 0; j--){mn = min(mn, x[j]);mx = max(mx, x[j]);}return mx - mn;}void sub1(vl &x, ll n, ll m){ll k, h, ans;// cin >> k >> s;h = min(m, n);for(k = 1; k <= m; k++){vl v(k, 1);ans = x[n-1];while(v.size() >= 1){if (v.size() <= h){// outp(v);ans = min(ans, cal(x, v));}if (v.size() == 1) break;ll j = v.size()-1, i = v.size()-2;if ((v[i]+1)*3 <= v[i]+v[j]){ll m, t = v[j];m = v[j] = ++v[i];t -= 1 + m;while(t >= 2*m){v.push_back(m);t -= m;}v.push_back(t);}else if (v[i]+1 < v[j]){v[i]++, v[j]--;}else{v[i] += v[j];v.pop_back();}}cout << ans << " ";}cout << "\n";}int main(){ios_base::sync_with_stdio(false);cin.tie(0); cout.tie(0);multiset <ll> s;ll n, m, i, j, k, a, b, r, t, f = 0, c, mn, S = 0;vpl ap;cin >> n >> m;vl x(n);for(i = 0; i < n; i++){cin >> x[i];S += x[i];}sort(x.begin(), x.end());if (m <= 10){sub1(x, n, m);return 0;}// ap.push_back({x[0], 1});// mn = x[0];// for(i = 1; i < n; i++)// {// if(x[i] == x[i-1])// ap.back().se++;// else// ap.push_back({x[i], 1});// }for(i = 0; i < n; i++){s.insert(x[i]);}t = m;for(k = 1; k <= t; k++){if(s.size() == 1){a = *s.begin();cout << (a % (k + 1) != 0) << " ";continue;}//cerr << k << ": ";m = k - f;while(m){//for(auto x : s)//cerr << x << " ";//cerr << "\n";//cerr << "size: " << s.size() << "\n";//cerr << a << " " << b << "\n";auto it = s.end(); it--; a = *it;b = *s.begin();if(a == b){c = s.size();a = a / (m / c + 1) + (a % (m / c + 1) != 0);b = b / (m / c + (m % c != 0) + 1);m = 0;}else{c = 0;//cerr << a << "!!!!!";while(*it == a){it--;c++;}b = *it;if(m >= (a / b) * c){m -= (a / b) * c;f += (a / b) * c;it++;s.erase(it, s.end());//cerr << "*1";i = a / b + 1;r = a % i;while(c--){for(j = 1; j <= r; j++)s.insert(a / i + 1);for(j = r + 1; j <= i; j++)s.insert(a / i);}it = s.end();it--; a = *it;it = s.begin(); b = *it;//cerr << ": " << a << " " << b << "\n";}else{//cerr << "*2";i = b;b = min(a / (m / c + (m % c != 0) + 1), *s.begin());a = max(i, a / (m / c + 1) + ((a % (m / c + 1)) != 0));m = 0;//cerr << ": " << a << " " << b << "\n";}}}//cerr << a << " " << b << ": ";cout << a - b << " ";}//for(auto x : s)//cerr << x << " ";return 0;}
Test details
Test 1
Group: 1, 3, 4, 5, 6
Verdict: ACCEPTED
input |
---|
1 1 6 |
correct output |
---|
0 |
user output |
---|
0 |
Test 2
Group: 1, 4, 5, 6
Verdict: ACCEPTED
input |
---|
5 10 4 8 6 2 7 |
correct output |
---|
5 4 2 2 2 1 1 1 1 1 |
user output |
---|
5 4 2 2 2 1 1 1 1 1 |
Test 3
Group: 1, 4, 5, 6
Verdict: ACCEPTED
input |
---|
5 10 5 5 8 6 7 |
correct output |
---|
3 3 2 3 2 2 1 1 1 2 |
user output |
---|
3 3 2 3 2 2 1 1 1 2 |
Test 4
Group: 1, 4, 5, 6
Verdict: ACCEPTED
input |
---|
5 10 8 7 9 6 10 |
correct output |
---|
4 4 3 3 2 2 1 2 2 1 |
user output |
---|
4 4 3 3 2 2 1 2 2 1 |
Test 5
Group: 2, 5, 6
Verdict: ACCEPTED
input |
---|
1000 1071 3 2 3 1 3 3 2 3 2 3 2 2 2 1 2 ... |
correct output |
---|
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
user output |
---|
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
Test 6
Group: 2, 5, 6
Verdict: ACCEPTED
input |
---|
1000 1500 3 2 2 3 2 3 2 2 2 3 2 2 3 3 3 ... |
correct output |
---|
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
user output |
---|
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ... |
Test 7
Group: 3, 5, 6
Verdict: ACCEPTED
input |
---|
1000 2 15 710 210 347 398 66 318 277 ... |
correct output |
---|
994 994 |
user output |
---|
994 994 |
Test 8
Group: 3, 5, 6
Verdict: ACCEPTED
input |
---|
1000 2 743 890 592 942 736 969 616 50... |
correct output |
---|
498 496 |
user output |
---|
498 496 |
Test 9
Group: 3, 5, 6
Verdict: ACCEPTED
input |
---|
1000 2 987 968 920 994 988 918 914 95... |
correct output |
---|
500 500 |
user output |
---|
500 500 |
Test 10
Group: 3, 5, 6
Verdict: ACCEPTED
input |
---|
1000 2 996 1000 998 998 999 997 997 9... |
correct output |
---|
500 500 |
user output |
---|
500 500 |
Test 11
Group: 3, 5, 6
Verdict: ACCEPTED
input |
---|
1000 2 501 501 501 501 501 501 501 50... |
correct output |
---|
1 168 |
user output |
---|
1 168 |
Test 12
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 200 145 136 74 83 73 36 196 115 11... |
correct output |
---|
194 190 189 183 182 181 181 17... |
user output |
---|
194 190 189 183 182 181 181 17... |
Test 13
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 200 157 110 168 155 192 107 146 15... |
correct output |
---|
95 96 96 95 93 94 94 94 90 91 ... |
user output |
---|
95 96 96 95 93 94 94 94 90 91 ... |
Test 14
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
50 200 137 118 160 118 146 160 140 18... |
correct output |
---|
98 98 98 96 90 91 88 88 84 86 ... |
user output |
---|
98 98 98 96 90 91 88 88 84 86 ... |
Test 15
Group: 4, 5, 6
Verdict: WRONG ANSWER
input |
---|
100 200 147 174 186 148 155 128 158 18... |
correct output |
---|
99 99 98 98 97 97 96 96 95 95 ... |
user output |
---|
99 99 98 98 97 97 96 96 95 95 ... |
Test 16
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
1000 2000 928772177 816188227 216592201 ... |
correct output |
---|
991676844 990940224 990685481 ... |
user output |
---|
991676844 990940224 990685481 ... |
Test 17
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
1000 2000 665759876 597950008 615453266 ... |
correct output |
---|
498801198 498681904 498504321 ... |
user output |
---|
498801198 498681904 498504321 ... |
Test 18
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
500 2000 683288817 784230412 626685186 ... |
correct output |
---|
497667621 498434895 495465990 ... |
user output |
---|
497667621 498434895 495465990 ... |
Test 19
Group: 5, 6
Verdict: WRONG ANSWER
input |
---|
1000 2000 666667000 809309500 571572000 ... |
correct output |
---|
499499500 499249250 498999000 ... |
user output |
---|
499499500 499249250 498999000 ... |
Test 20
Group: 6
Verdict: WRONG ANSWER
input |
---|
100000 200000 861772559 734298084 983382252 ... |
correct output |
---|
499973914 499985299 499985141 ... |
user output |
---|
499973914 499985299 499985141 ... |
Test 21
Group: 6
Verdict: WRONG ANSWER
input |
---|
30000 200000 691834579 617419813 514778075 ... |
correct output |
---|
499967533 499976270 499969810 ... |
user output |
---|
499967533 499976270 499969810 ... |
Test 22
Group: 6
Verdict: WRONG ANSWER
input |
---|
100000 200000 820255000 960780000 741965000 ... |
correct output |
---|
499995000 499992500 499990000 ... |
user output |
---|
499995000 499992500 499990000 ... |