QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #372073 | #1280. Fibonacci Partition | Rong7 | WA | 305ms | 3860kb | C++14 | 9.8kb | 2024-03-30 21:00:57 | 2024-03-30 21:01:38 |
Judging History
answer
// Not afraid to dark.
#include <bits/stdc++.h>
using namespace std;
clock_t start_time, end_time;
#define GET_START start_time = clock ();
#define GET_END end_time = clock (); fprintf (stderr, "TIME COSSEMED : %0.3lf\n", 1.0 * (end_time - start_time) / CLOCKS_PER_SEC);
#define int long long
namespace io {
int read_pos, read_dt; char read_char;
__inline__ __attribute__ ((always_inline)) int read (int &p = read_pos){
p = 0, read_dt = 1; read_char = getchar ();
while (! isdigit (read_char)){
if (read_char == '-')
read_dt = - 1;
read_char = getchar ();
}
while (isdigit (read_char)){
p = (p << 1) + (p << 3) + read_char - 48;
read_char = getchar ();
}
return p = p * read_dt;
}
int write_sta[65], write_top;
__inline__ __attribute__ ((always_inline)) void write (int x){
if (x < 0)
putchar ('-'), x = - x;
write_top = 0;
do
write_sta[write_top ++] = x % 10, x /= 10;
while (x);
while (write_top)
putchar (write_sta[-- write_top] + 48);
}
int llen;
__inline__ __attribute__ ((always_inline)) int get_string (char c[], int &len = llen){
len = 0;
read_char = getchar ();
while (read_char == ' ' || read_char == '\n' || read_char == '\r')
read_char = getchar ();
while (read_char != ' ' && read_char != '\n' && read_char != '\r'){
c[++ len] = read_char;
read_char = getchar ();
}
return len;
}
}
#define vic(x) ((x & 1) ? - 1 : 1)
const int V = 1e9, inf = 0x3f3f3f3f3f3f3f3fll;
int Luc[105], cnt;
__inline__ __attribute__ ((always_inline)) void INIT (){
Luc[0] = 2;
Luc[1] = 1;
for (cnt = 1;Luc[cnt] <= V;++ cnt)
Luc[cnt + 1] = Luc[cnt] + Luc[cnt - 1];
-- cnt;
}
int ans;
struct node {
int l, r;
node (int _l_ = 0, int _r_ = 0){
l = _l_;
r = _r_;
}
__inline__ __attribute__ ((always_inline)) bool operator < (const node &oth) const {
if (l == oth.l)
return r < oth.r;
return l < oth.l;
}
};
set < node > s;
namespace CHECK {
__inline__ __attribute__ ((always_inline)) void OUTPUT (){
printf ("<%lld>", ans);
for (auto x : s)
printf ("[%lld %lld]", x.l, x.r);
puts ("");
}
}
__inline__ __attribute__ ((always_inline)) set < node > ::iterator find_right (int x){
return s.upper_bound (node (x, inf));
}
__inline__ __attribute__ ((always_inline)) set < node > ::iterator find_contain (int x){
auto it = find_right (x);
if (it == s.begin ())
return s.end ();
-- it;
if ((*it).r >= x)
return it;
return s.end ();
}
__inline__ __attribute__ ((always_inline)) set < node > ::iterator find_left (int x){
auto it = find_right (x);
if (it != s.begin ())
-- it;
if (it == s.end ())
return it;
if ((*it).r >= x && it != s.begin ())
return -- it;
if (it == s.begin () && (*it).r >= x)
return s.end ();
return it;
}
// __inline__ __attribute__ ((always_inline)) bool Check_first (node x){
// return find_left (x.l) == s.end ();
// }
__inline__ __attribute__ ((always_inline)) int Cost (node x){ // self cost
if (x.l <= 3)
return ((x.r - x.l) >> 1);
return x.r - x.l;
}
__inline__ __attribute__ ((always_inline)) int Cost_con (node x, node y){ // connect cost
int las = x.r - 1;
if (x.l <= 3)
++ las;
if (y.l - las <= 2)
return 1;
return (y.l - las + 1) / 2;
}
__inline__ __attribute__ ((always_inline)) void Del (node x){
if (x.l > x.r)
return ;
auto bel = find_contain (x.l);
node tt = *bel;
s.erase (bel);
if (tt.l <= x.l - 2)
s.insert (node (tt.l, x.l - 2));
if (x.r + 2 <= tt.r)
s.insert (node (x.r + 2, tt.r));
auto pre = find_left (x.l);
// printf ("del : %lld %lld\n", x.l, x.r);
// printf ("before : "); CHECK::OUTPUT ();
if (pre != s.end ())
ans -= Cost_con (*pre, x);
else
ans -= Cost_con (node (1, 1), x);
auto nex = find_right (x.r);
if (nex != s.end ())
ans -= Cost_con (x, *nex);
// CHECK::OUTPUT ();
if (pre != s.end () && nex != s.end ())
ans += Cost_con (*pre, *nex);
else
if (nex != s.end ())
ans += Cost_con (node (1, 1), *nex);
// CHECK::OUTPUT ();
ans -= Cost (x);
// CHECK::OUTPUT ();
// puts ("del end");
}
void Ins (node x){
if (x.l > x.r)
return ;
auto pre = find_left (x.l), nex = find_right (x.r);
// printf ("ins : %lld %lld\n", x.l, x.r);
if (pre != s.end () && (*pre).r == x.l - 2){
node tt;
Del (tt = *pre);
Ins (node (tt.l, x.r));
return ;
}
if (nex != s.end () && (*nex).l == x.r + 2){
node tt;
Del (tt = *nex);
Ins (node (x.l, tt.r));
return ;
}
// printf ("ins : %lld %lld\n", x.l, x.r);
// printf ("before : ");
// CHECK::OUTPUT ();
if (pre != s.end ())
ans += Cost_con (*pre, x);
else
ans += Cost_con (node (1, 1), x);
// CHECK::OUTPUT ();
if (nex != s.end ())
ans += Cost_con (x, *nex);
if (pre != s.end () && nex != s.end ())
ans -= Cost_con (*pre, *nex);
else
if (nex != s.end ())
ans -= Cost_con (node (1, 1), *nex);
ans += Cost (x);
s.insert (x);
// CHECK::OUTPUT ();
// puts ("ins end");
}
void Insert (int v, int p){
if (p < 1)
return ;
// printf ("<%lld %lld>\n", v, p);
if (v == 1){
set < node > ::iterator it;
if ((it = find_contain (p)) != s.end ()){
node tt = *it;
if ((p & 1) == (tt.l & 1)){
Del (tt);
Ins (node (tt.l + 1, p - 1));
Insert (1, tt.r + 1);
Insert (1, tt.l - 2);
} else {
Del (tt);
Ins (node (tt.l, p - 1));
Insert (1, tt.r + 1);
}
} else
if ((it = find_left (p)) != s.end () && (*it).r == p - 1){
node tt = *it;
Del (tt);
Ins (node (tt.l, tt.r - 2));
Insert (1, tt.r + 2);
} else
if ((it = find_right (p)) != s.end () && (*it).l == p + 1){
// puts ("in");
node tt = *it;
Del (tt);
Insert (1, tt.r + 1);
} else
Ins (node (p, p));
} else {
set < node > ::iterator it;
if ((it = find_contain (p)) != s.end ()){
node tt = *it;
if ((p & 1) == (tt.l & 1)){
Del (tt);
Ins (node (tt.l, p - 2));
Ins (node (p + 2, tt.r));
} else {
Insert (- 1, p + 1);
Insert (1, p - 1);
}
} else {
// exist prefix
it = find_right (p);
node tt = *it;
// CHECK::OUTPUT ();
Del (tt);
// CHECK::OUTPUT ();
Ins (node (tt.l + 2, tt.r));
int tl = tt.l - 1, u = p + 1;
if ((u & 1) != (tl & 1))
++ u;
Ins (node (u, tl));
if (u != p + 1)
Insert (1, p - 1);
}
}
}
__inline__ __attribute__ ((always_inline)) void WORK (){
for (int T = io::read (), x, y;T --;){
io::read (x), io::read (y);
++ y;
if (! x)
goto put_ans;
// Insert (x, y);
// goto put_ans;
{
int v = x / abs (x);
x = abs (x);
for (int i = cnt;i > 1;-- i)
if (Luc[i] <= x){
x -= Luc[i];
if (v > 0){
Insert (v, y + i);
Insert (v * vic (i), abs (y - i));
} else {
Insert (v * vic (i), abs (y - i));
Insert (v, y + i);
}
}
for (int i = 0;i < 2;++ i)
if (Luc[i] <= x){
x -= Luc[i];
if (v > 0){
Insert (v, y + i);
// if (y == 6)
// printf ("%lld %lld : ", v * vic (i), abs (y - i)), CHECK::OUTPUT ();
Insert (v * vic (i), abs (y - i));
// if (y == 6)
// printf ("%lld %lld : ", v, y + i), CHECK::OUTPUT ();
} else {
Insert (v * vic (i), abs (y - i));
// if (y == 6)
// printf ("%lld %lld : ", v * vic (i), abs (y - i)), CHECK::OUTPUT ();
Insert (v, y + i);
// if (y == 6)
// printf ("%lld %lld : ", v, y + i), CHECK::OUTPUT ();
}
}
if (! s.empty () && (*s.begin ()).l == 1)
Del (node (1, 1)), Insert (1, 2);
}
put_ans : ;
// CHECK::OUTPUT ();
io::write (ans), puts ("");
}
}
signed main (){
GET_START
INIT ();
for (int T = io::read ();T --;)
WORK (); // remember to initialize the data
GET_END
return 0;
}
/*
ex :
in:
1 5
1 1
1 3
1 6
1 9
1 5
out:
1
2
4
6
?[2 4][8 10]
example :
input :
1
19
1 1
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
-2 5
2 5
-1 8
-1 7
-1 6
-1 5
-1 4
-1 3
-1 2
-1 1
output :
1
1
2
2
3
3
4
4
5
6
5
4
4
3
3
2
2
1
*/
// 1 2 1 2 1 2
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3860kb
input:
1 10 1 1 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 -2 5
output:
1 1 2 2 3 3 4 4 5 6
result:
ok 10 tokens
Test #2:
score: -100
Wrong Answer
time: 305ms
memory: 3816kb
input:
8954 6 912254245 4 -1 46 -12 36 893871732 9 803228012 6 -2420954 6 1 84415313 5 8 968295352 9 61184346 7 461451639 3 678826278 4 108032410 3 515272015 4 879628340 3 85675803 7 2 704915698 4 222546290 5 2 163176069 7 336268000 4 5 186521340 8 -1974 23 139542303 7 799104511 3 273699125 5 9 343587584 7...
output:
33 31 30 38 40 35 37 38 39 37 38 36 40 37 41 37 40 43 42 38 35 39 37 37 39 41 36 39 40 36 38 42 39 44 42 36 35 36 37 37 34 36 38 39 41 41 44 40 37 40 41 38 37 38 39 39 42 40 36 35 38 37 45 39 38 39 37 37 34 39 37 35 37 42 36 39 38 40 38 40 37 42 36 42 37 36 39 41 44 40 38 42 38 39 42 42 38 41 40 40 ...
result:
wrong answer 1st words differ - expected: '34', found: '33'