QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #617423 | #1958. Grid Triangle | Afterlife# | AC ✓ | 1ms | 3804kb | C++20 | 5.0kb | 2024-10-06 15:30:13 | 2024-10-06 15:30:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void upd(int &x,int y) {
x = min(x , y);
}
ll S(int l,int r) {
return 1LL*r*(r + 1) / 2 - 1LL*l*(l-1)/2;
}
ll solve(int a,int b,int c) {
// printf("%d %d %d : ",a,b,c);
a = min(a , b - 1);
a = min(a , (c + 1) / 2 - 1) ;
ll ans = 0;
if(c - b >= 1) {
int r = min(a , c - b);
ans += 1LL * r * b;
ans -= 1LL * S(1 , r) ;
}
int lp = max(1 , c -b + 1) ;
if(lp <= a) {
ans += 1LL * (a - lp + 1) * c;
ans -= 2LL * S(lp , a) ;
}
// printf("%lld\n",ans) ;
return ans;
}
void output(__int128 x) {
if(x < 10) {
cout << (int)(x % 10);
return;
}
output(x / 10);
cout << (int)(x % 10);
}
int main() {
int a, b, c;
cin >> a >> b >> c;
__int128 ans = 0;
vector<vector<int> > v;
// v.push_back(vector<int>{0 , 1 , 1});
// v.push_back(vector<int>{1 , 1 , 2});
v.push_back(vector<int>{1 , 2 , 3});
v.push_back(vector<int>{1 , 2 , 4});
vector<int> g(4) ;
g[1] = a;g[2] = b;g[3] = c;
set<vector<int> > sv;
for(auto &x : v ) {
auto p1 = x;
do{
auto p2 = x;
do{
for(int s1 = 0;s1 < (1 << 3);s1++) {
for(int s2 = 0;s2 < (1<<3);s2++) {
bool ff=1;
auto p3 = p1;
auto p4 = p2;
for(int i = 0;i < 3;i++) {
if(((s1 >> i) & 1) && p1[i] == 0) {ff = 0;}
if((s1 >> i) & 1) p3[i] *= -1;
if(((s2 >> i) & 1) && p2[i] == 0) {ff = 0;}
if((s2 >> i) & 1) p4[i] *= -1;
}
if(!ff) continue ;
auto p5 = p3;
for(int i = 0;i < 3;i++) {
p5[i] = abs(p5[i] - p4[i]);
}
sort(p5.begin() , p5.end()) ;
if(p5 != x) continue;
if(x==(vector<int>{1 , 2 , 4})) {
int lm = 1e9;
if(p3[0]) lm = min(lm , a / abs(p3[0]));
if(p3[1]) lm = min(lm , b / abs(p3[1]));
if(p3[2]) lm = min(lm , c / abs(p3[2]));
if(p4[0]) lm = min(lm , a / abs(p4[0]));
if(p4[1]) lm = min(lm , b / abs(p4[1]));
if(p4[2]) lm = min(lm , c / abs(p4[2]));
ans += lm;
}
else {
vector<int> lm(4 , 1e9) ;
for(int i = 0;i < 3;i++) {
upd(lm[abs(p3[i])] , g[i + 1]) ;
upd(lm[abs(p4[i])] , g[i + 1]) ;
}
ans += solve(lm[1] , lm[2] , lm[3]);
}
// vector<int> cur;
// for(int j = 1 ; j <= lm;j++) {
// assert(abs(p3[0]) * lm <= a);
// assert(abs(p3[1]) * lm <= b);
// assert(abs(p3[2]) * lm <= c);
// assert(abs(p4[0]) * lm <= a);
// assert(abs(p4[1]) * lm <= b);
// assert(abs(p4[2]) * lm <= c);
// for(int k = 0;k < 3;k++) cur.push_back(p3[k] * j);
// for(int k = 0;k < 3;k++) cur.push_back(p4[k] * j);
// }
// printf("%d %d %d : %d %d %d : %d\n",p3[0],p3[1],p3[2] ,p4[0],p4[1],p4[2] , lm) ;
// if(sv.count(cur)) {
// puts("WA") ; exit(0) ;
// }
// sv.insert(cur) ;
// ans += lm;
}
}
}while(next_permutation(p2.begin() , p2.end()));
}while(next_permutation(p1.begin() , p1.end()));
}
// for(auto &cur : sv) {
// vector<int> p1,p2,p3;
// for(int i = 0;i < 3;i++) p1.push_back(cur[i]);
// for(int i = 0;i < 3;i++) p2.push_back(cur[i + 3]);
// for(int i = 0;i < 3;i++) p3.push_back(p1[i] - p2[i]) ;
// for(auto &x : p1) x = abs(x);
// for(auto &x : p2) x = abs(x);
// for(auto &x : p3) x = abs(x);
// sort(p1.begin() , p1.end());
// sort(p2.begin() , p2.end());
// sort(p3.begin() , p3.end());
// assert(p1 == p2 && p2 == p3) ;
// }
ans /= 2;
// for(int i = 3 ; i <= min({a , b , c}) ; i++) {
// printf("%d %d\n",i,(i-2)-(i%2==0)) ;
// ans += (i - 2) - (i % 2 == 0) ;
// }
output(ans);
cout<<"\n";
// cout << ans << '\n' ; return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3604kb
input:
1 1 4
output:
0
result:
ok single line: '0'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3768kb
input:
1 1 5
output:
0
result:
ok single line: '0'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3580kb
input:
1 2 6
output:
0
result:
ok single line: '0'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
1 2 7
output:
0
result:
ok single line: '0'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3724kb
input:
2 2 8
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
2 3 9
output:
16
result:
ok single line: '16'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
2 3 10
output:
16
result:
ok single line: '16'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
2 3 11
output:
16
result:
ok single line: '16'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3604kb
input:
3 4 12
output:
64
result:
ok single line: '64'
Test #10:
score: 0
Accepted
time: 1ms
memory: 3676kb
input:
3 4 13
output:
64
result:
ok single line: '64'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3772kb
input:
3 4 14
output:
64
result:
ok single line: '64'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3464kb
input:
3 5 15
output:
80
result:
ok single line: '80'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
10000000 10000000 10000000
output:
1199999760000000
result:
ok single line: '1199999760000000'
Test #14:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
7663341 2799917 6434354
output:
125432496112224
result:
ok single line: '125432496112224'
Test #15:
score: 0
Accepted
time: 1ms
memory: 3760kb
input:
5847310 6503054 3563307
output:
196607948002960
result:
ok single line: '196607948002960'
Test #16:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
3131008 7950384 757301
output:
9176058698400
result:
ok single line: '9176058698400'
Test #17:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
9570661 9593872 9917084
output:
1100945395924880
result:
ok single line: '1100945395924880'
Test #18:
score: 0
Accepted
time: 1ms
memory: 3532kb
input:
3510873 8095808 2299177
output:
79848923155584
result:
ok single line: '79848923155584'
Test #19:
score: 0
Accepted
time: 1ms
memory: 3572kb
input:
7476400 3286922 144073
output:
332109011520
result:
ok single line: '332109011520'
Test #20:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
2528777 8583320 3053921
output:
86257168366272
result:
ok single line: '86257168366272'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
756027 9877774 6224461
output:
9145211051024
result:
ok single line: '9145211051024'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3788kb
input:
1799348 1545770 5903860
output:
31551400528464
result:
ok single line: '31551400528464'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3512kb
input:
2866047 8448813 9201454
output:
131427537714224
result:
ok single line: '131427537714224'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3576kb
input:
3253 19822 15760
output:
169234080
result:
ok single line: '169234080'
Test #25:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
18973 6799 2004
output:
64208160
result:
ok single line: '64208160'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
1607 25903 7685
output:
41280624
result:
ok single line: '41280624'
Test #27:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
8763 27091 27201
output:
1228432400
result:
ok single line: '1228432400'
Test #28:
score: 0
Accepted
time: 1ms
memory: 3804kb
input:
3275 1018 17315
output:
16556752
result:
ok single line: '16556752'
Test #29:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
31480 24767 5816
output:
541074112
result:
ok single line: '541074112'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3628kb
input:
22046 8058 12456
output:
985126032
result:
ok single line: '985126032'
Test #31:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
10321 22446 10938
output:
1327450496
result:
ok single line: '1327450496'
Test #32:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
14930 18763 2124
output:
72131040
result:
ok single line: '72131040'
Test #33:
score: 0
Accepted
time: 1ms
memory: 3800kb
input:
18366 14707 1959
output:
61355888
result:
ok single line: '61355888'
Test #34:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
4 4 4
output:
96
result:
ok single line: '96'
Test #35:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
5 5 5
output:
192
result:
ok single line: '192'
Test #36:
score: 0
Accepted
time: 1ms
memory: 3728kb
input:
6 6 6
output:
288
result:
ok single line: '288'
Test #37:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
7 7 7
output:
432
result:
ok single line: '432'
Test #38:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
8 8 8
output:
576
result:
ok single line: '576'
Test #39:
score: 0
Accepted
time: 1ms
memory: 3764kb
input:
9 9 9
output:
768
result:
ok single line: '768'
Test #40:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
10 10 10
output:
960
result:
ok single line: '960'