Simmetrik Tikinti#12309
Daxil ol

Simmetrik Tikinti

6 saniyə
1.024 meqabayt
Çətin

Tam ədəd verilir və bir array haqqında məlumat, hər bir məlumat üç tam ədəd ehtiva edir, burada:

Sizin vəzifəniz, bütün verilmiş məlumatları təmin edən istənilən uzunluğu olan bir array yaratmaqdır, əgər mümkün deyilsə çap edin.

Bundan əlavə, (0 \le a_i \le 10^{18}) şərti olmalıdır.

Bir array simmetrik adlanır, əgər i_{th} elementinin soldan və i_{th} elementinin sağdan cəmi arrayda ortaq bir dəyər cəminə malikdirsə.

məsələn: a=[15,10,20,15] simmetrikdir, çünki a_1+a_{-1}=15+15=a_2+a_{-2}=10+20=30. amma a=[3,7,3] simmetrik deyil, çünki a_{1}+a_{-1}=6 və a_2+a_{-2}=7+7=14.

Giriş

Birinci sətir tək bir tam ədəd (1 \le t \le 10^4) - test hallarının sayını ehtiva edir.

Hər bir test halının birinci sətiri iki tam ədəd (1 \le n,q \le 10^6) - array -nın uzunluğu və sorğuların sayını ehtiva edir.

Sonrakı sətiri üç tam ədəd (1 \le l \le r \le n ; 0 \le x \le 1) - məlumatdakı alt array sərhədləri və alt arrayın vəziyyəti.

və cəminin 2\cdot 10^6-dan çox olmayacağına zəmanət verilir.

Məlumatda heç bir interval bir dəfədən çox görünməyəcək, rəsmi olaraq (l_i,r_i) cüt şəkildə fərqlidir.

Çıxış

Hər bir test halı üçün, əgər belə bir array varsa, SİZ TAM XÜSUSİ SMT HƏLL EDİCİSİ (DPLL(T)) İCRA ETMƏLİSİNİZ: hər "simmetrik" sorğunu güzgü cüt cəmləri bərabərliklərinin birləşməsi kimi kodlaşdırın, hər "simmetrik deyil" sorğunu bu bərabərliklərdən ən az birinin yanlış olmasını məcbur edən bir disyunksiyaya kodlaşdırın, sonra bir CDCL SAT nüvəsi ilə bənd öyrənmə və izlənilən ədədlərlə işləyin, eyni zamanda artımlı geri çəkilə bilən xətti-aritmetik nəzəri modul (izah yaradılması ilə sıx Qaus eliminasiya) cari doğru bərabərlikləri təsdiqləyir və münaqişə bəndləri çıxarır; yalnız SAT+teoriya yaxınlaşdıqdan sonra siz məhdudlaşdırılmış tam ədəd modelini çıxara bilərsiniz hər hansı bir array çap edin, əks halda çap edin.

Nümunələr

Nümunə 1

Loading
Loading

Qeyd

Qeyd

Birinci test halında, a = [9,5,7,5,8] bütün məlumatları təmin etdiyi üçün düzgündür.

  1. Məlumat 1: (l,r,x) = (1,4,0) deməkdir ki, alt array [a_1,a_2,a_3,a_4] simmetrik deyil. Bu, [9,5,7,5]-in

    a_1 + a_4 = 9 + 5 = 14,\qquad a_2 + a_3 = 5 + 7 = 12,

    bərabər olmadığını təmin edir, buna görə də alt array simmetrik deyil.

  2. Məlumat 2: (l,r,x) = (4,5,1) deməkdir ki, alt array [a_4,a_5] simmetrikdir. Bu, uzunluğu olan bir alt array üçün yalnız bir dəyərin olduğunu təmin edir:

    a_4 + a_5 = 5 + 8 = 13.

Beləliklə, bu düzgündür.

İkinci test halında, a = [1,2,3,4,5] bütün məlumatları təmin etdiyi üçün düzgündür.

  1. Məlumat 1: (1,3,1) deməkdir ki, alt array [1,2,3] simmetrikdir. Bu, təmin edilir, çünki

    a_1 + a_3 = 1 + 3 = 4,\qquad a_2 + a_2 = 2 + 2 = 4.

  2. Məlumat 2: (1,4,1) deməkdir ki, alt array [1,2,3,4] simmetrikdir. Bu, təmin edilir, çünki

    a_1 + a_4 = 1 + 4 = 5,\qquad a_2 + a_3 = 2 + 3 = 5.

  3. Məlumat 3: (1,5,1) deməkdir ki, alt array [1,2,3,4,5] simmetrikdir. Bu, təmin edilir, çünki

    a_1 + a_5 = 1 + 5 = 6,\qquad a_2 + a_4 = 2 + 4 = 6,\qquad a_3 + a_3 = 3 + 3 = 6.

  4. Məlumat 4: (2,4,1) deməkdir ki, alt array [2,3,4] simmetrikdir. Bu, təmin edilir, çünki

    a_2 + a_4 = 2 + 4 = 6,\qquad a_3 + a_3 = 3 + 3 = 6.

  5. Məlumat 5: (2,5,1) deməkdir ki, alt array [2,3,4,5] simmetrikdir. Bu, təmin edilir, çünki

    a_2 + a_5 = 2 + 5 = 7,\qquad a_3 + a_4 = 3 + 4 = 7.

  6. Məlumat 6: (3,5,1) deməkdir ki, alt array [3,4,5] simmetrikdir. Bu, təmin edilir, çünki

    a_3 + a_5 = 3 + 5 = 8,\qquad a_4 + a_4 = 4 + 4 = 8.

Beləliklə, bu düzgündür.

Üçüncü test halında, belə bir arrayın mövcud olmadığını göstərmək mümkündür.

Bal hesablama

  1. Alt vəzifə ( xal): (1 \le n \le 10) və (q=\displaystyle \frac{n(n+1)}{2})

  2. Alt vəzifə ( xal): (n,q \le 10).

  3. Alt vəzifə ( xal): (\sum n+q \le 2000).

  4. Alt vəzifə ( xal): Hər məlumat üçün (x=1) şərti ödənilir.

  5. Alt vəzifə ( xal): Heç bir əlavə şərt yoxdur.