772.md (51080B)
1 Source: https://codeforces.com/blog/entry/51598 2 3 **Viscious Keyboard** 4 5 Tutorial is loading... 6 7 **example code 1** 8 9 ``` 10 print (lambda s: max((s[:i] + x + s[i+1:]).count("VK") for x in "VK" for i in range(len(s))))(raw_input()) 11 ``` 12 13 **example code 2** 14 15 ``` 16 print (lambda s: s.count("VK") + int(any(x*3 in "K" + s + "V" for x in "VK")))(raw_input()) 17 ``` 18 19 **Valued Keys** 20 21 Tutorial is loading... 22 23 **example code** 24 25 ``` 26 x,y = raw_input(), raw_input() 27 print all(a>=b for a,b in zip(x,y)) * y or "-1" 28 ``` 29 30 **Voltage Keepsake** 31 32 Tutorial is loading... 33 34 **example code (c++)** 35 36 ``` 37 #include <stdio.h> 38 #include <algorithm> 39 #include <assert.h> 40 using namespace std; 41 typedef long long ll; 42 typedef long double ld; 43 // Adjust MAXN for bounds 44 const ll MAXN=1e5+4; 45 // MAXV is the max amount of time we can take 46 const ld MAXV=1e18; 47 ll a[MAXN],b[MAXN]; 48 ld exhaust[MAXN]; 49 int n; 50 ll P; 51 bool f(ld imid) { 52 ld needsum=0; 53 for (int i=0;i<n;i++) { 54 ld need=max(0.0L, (imid-exhaust[i])*a[i]); 55 needsum+=need; 56 } 57 ld supply=imid*P; 58 return supply>=needsum; 59 } 60 int main() 61 { 62 scanf("%d%lld",&n,&P); 63 for (int i=0;i<n;i++) { 64 scanf("%lld%lld",&a[i],&b[i]); 65 } 66 ll suma=0; 67 for (int i=0;i<n;i++) { 68 suma+=a[i]; 69 } 70 if (P>=suma) { 71 printf("-1\n"); 72 return 0; 73 } 74 for (int i=0;i<n;i++) { 75 exhaust[i]=((ld)b[i])/((ld)a[i]); 76 } 77 ld imin=0,imax=MAXV; 78 for (ll iter=0;iter<220;iter++) { 79 ld imid=(imin+imax)/2; 80 if (f(imid)) imin=imid; 81 else imax=imid; 82 } 83 if (imax>MAXV-100) printf("-1\n"); 84 else printf("%.9f\n",(double)imin); 85 } 86 ``` 87 88 **Volatile Kite** 89 90 Tutorial is loading... 91 92 **example code (c++)** 93 94 ``` 95 #include <bits/stdc++.h> 96 using namespace std; 97 #define sim template < class c 98 #define ris return * this 99 #define dor > debug & operator << 100 #define eni(x) sim > typename \ 101 enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { 102 sim > struct rge {c b, e; }; 103 sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } 104 sim > auto dud(c* x) -> decltype(cerr << *x, 0); 105 sim > char dud(...); 106 struct debug { 107 #ifdef LOCAL 108 ~debug() { cerr << endl; } 109 eni(!=) cerr << boolalpha << i; ris; } 110 eni(==) ris << range(begin(i), end(i)); } 111 sim, class b dor(pair < b, c > d) { 112 ris << "(" << d.first << ", " << d.second << ")"; 113 } 114 sim dor(rge<c> d) { 115 *this << "["; 116 for (auto it = d.b; it != d.e; ++it) 117 *this << ", " + 2 * (it == d.b) << *it; 118 ris << "]"; 119 } 120 #else 121 sim dor(const c&) { ris; } 122 #endif 123 }; 124 #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " 125 126 typedef long double ld; 127 typedef long double ll; 128 129 ld K(ld a) { return a * a; } 130 131 struct P { 132 ll x, y; 133 void read() { cin >> x >> y; } 134 P operator + (P b) { return P{x + b.x, y + b.y}; } 135 P operator - (P b) { return P{x - b.x, y - b.y}; } 136 P operator * (ld/*ll*/ mul) { return P{x * mul, y * mul}; } 137 ll operator * (P b) { return x * b.y - y * b.x; } 138 ll dot(P b) { return x * b.x + y * b.y; } 139 ld len() { return sqrt(K(x) + K(y)); } 140 P lenTo(ld to) { return *this * (to / len()); } 141 ld dist(P & b) { return (*this - b).len(); } 142 }; 143 144 struct L2 { 145 P one, two; 146 ld dist(P he) { 147 return abs((he - one) * (he - two)) / one.dist(two); 148 } 149 }; 150 151 int main() { 152 int n; 153 cin >> n; 154 vector<P> points(n); 155 for(P & p : points) 156 p.read(); 157 ld answer = 1e15; 158 for(int i = 0; i < n; ++i) 159 for(int j = 0; j < 2 * n; ++j) 160 if(abs(i - j) <= 2) 161 for(int k = 0; k < 2 * n; ++k) 162 if(abs(i - k) <= 2 && (int) set<int>{i % n, j % n, k % n}.size() == 3) 163 answer = min(answer, L2{points[i%n], points[j%n]}.dist(points[k%n])); 164 printf("%.10lf\n", (double) answer / 2); 165 } 166 ``` 167 168 **example code (java)** 169 170 ``` 171 import java.io.OutputStream; 172 import java.io.IOException; 173 import java.io.InputStream; 174 import java.io.OutputStream; 175 import java.io.PrintWriter; 176 import java.io.BufferedWriter; 177 import java.io.Writer; 178 import java.io.OutputStreamWriter; 179 import java.util.InputMismatchException; 180 import java.io.IOException; 181 import java.io.InputStream; 182 183 /** 184 * Built using CHelper plug-in 185 * Actual solution is at the top 186 */ 187 public class Main { 188 public static void main(String[] args) { 189 InputStream inputStream = System.in; 190 OutputStream outputStream = System.out; 191 InputReader in = new InputReader(inputStream); 192 OutputWriter out = new OutputWriter(outputStream); 193 NonConvexPolygon solver = new NonConvexPolygon(); 194 solver.solve(1, in, out); 195 out.close(); 196 } 197 198 static class NonConvexPolygon { 199 public void solve(int testNumber, InputReader in, OutputWriter out) { 200 int n = in.nextInt(); 201 long[][] p = new long[n][2]; 202 for (int i = 0; i < n; i++) { 203 p[i][0] = in.nextInt(); 204 p[i][1] = in.nextInt(); 205 } 206 double ans = 1L << 60; 207 for (int i = 0; i < n; i++) { 208 int prev = (i + n - 1) % n, next = (i + 1) % n; 209 ans = Math.min(ans, PointToSegmentDistance.pointToLineThroughTwoPointsDistance( 210 p[i][0], p[i][1], p[prev][0], p[prev][1], p[next][0], p[next][1] 211 ) / 2.0); 212 } 213 out.printf("%.10f\n", ans); 214 } 215 216 } 217 218 static class Utils { 219 public static double cross(Point a, Point b, Point c) { 220 Point ab = new Point(b.x - a.x, b.y - a.y); 221 Point ac = new Point(c.x - a.x, c.y - a.y); 222 return ab.x * ac.y - ab.y * ac.x; 223 } 224 225 } 226 227 static class PointToSegmentDistance { 228 static double fastHypot(double x, double y) { 229 return Math.sqrt(x * x + y * y); 230 } 231 232 public static double pointToLineThroughTwoPointsDistance(long x, long y, long ax, long ay, long bx, long by) { 233 double t = Utils.cross(new Point(ax, ay), new Point(bx, by), new Point(x, y)); 234 return Math.abs(t / fastHypot(ax - bx, ay - by)); 235 } 236 237 } 238 239 static class Point implements Comparable<Point> { 240 public double x; 241 public double y; 242 public double angle; 243 public int idx; 244 245 public Point(double x, double y) { 246 this.x = x; 247 this.y = y; 248 angle = 0; 249 } 250 251 public Point(double x, double y, int idx) { 252 this.x = x; 253 this.y = y; 254 this.idx = idx; 255 } 256 257 public int compareTo(Point other) { 258 return x == other.x ? (int) Math.signum(y - other.y) : (int) Math.signum(x - other.x); 259 } 260 261 } 262 263 static class OutputWriter { 264 private final PrintWriter writer; 265 266 public OutputWriter(OutputStream outputStream) { 267 writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); 268 } 269 270 public OutputWriter(Writer writer) { 271 this.writer = new PrintWriter(writer); 272 } 273 274 public void printf(String format, Object... objects) { 275 writer.printf(format, objects); 276 } 277 278 public void close() { 279 writer.close(); 280 } 281 282 } 283 284 static class InputReader { 285 private InputStream stream; 286 private byte[] buf = new byte[1024]; 287 private int curChar; 288 private int numChars; 289 290 public InputReader(InputStream stream) { 291 this.stream = stream; 292 } 293 294 public int read() { 295 if (this.numChars == -1) { 296 throw new InputMismatchException(); 297 } else { 298 if (this.curChar >= this.numChars) { 299 this.curChar = 0; 300 301 try { 302 this.numChars = this.stream.read(this.buf); 303 } catch (IOException var2) { 304 throw new InputMismatchException(); 305 } 306 307 if (this.numChars <= 0) { 308 return -1; 309 } 310 } 311 312 return this.buf[this.curChar++]; 313 } 314 } 315 316 public int nextInt() { 317 int c; 318 for (c = this.read(); isSpaceChar(c); c = this.read()) { 319 ; 320 } 321 322 byte sgn = 1; 323 if (c == 45) { 324 sgn = -1; 325 c = this.read(); 326 } 327 328 int res = 0; 329 330 while (c >= 48 && c <= 57) { 331 res *= 10; 332 res += c - 48; 333 c = this.read(); 334 if (isSpaceChar(c)) { 335 return res * sgn; 336 } 337 } 338 339 throw new InputMismatchException(); 340 } 341 342 public static boolean isSpaceChar(int c) { 343 return c == 32 || c == 10 || c == 13 || c == 9 || c == -1; 344 } 345 346 } 347 } 348 ``` 349 350 **Vulnerable Kerbals** 351 352 Tutorial is loading... 353 354 **example code (c++)** 355 356 ``` 357 #include <bits/stdc++.h> 358 using namespace std; 359 #define sim template < class c 360 #define ris return * this 361 #define dor > debug & operator << 362 #define eni(x) sim > typename \ 363 enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { 364 sim > struct rge {c b, e; }; 365 sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } 366 sim > auto dud(c* x) -> decltype(cerr << *x, 0); 367 sim > char dud(...); 368 struct debug { 369 #ifdef LOCAL 370 ~debug() { cerr << endl; } 371 eni(!=) cerr << boolalpha << i; ris; } 372 eni(==) ris << range(begin(i), end(i)); } 373 sim, class b dor(pair < b, c > d) { 374 ris << "(" << d.first << ", " << d.second << ")"; 375 } 376 sim dor(rge<c> d) { 377 *this << "["; 378 for (auto it = d.b; it != d.e; ++it) 379 *this << ", " + 2 * (it == d.b) << *it; 380 ris << "]"; 381 } 382 #else 383 sim dor(const c&) { ris; } 384 #endif 385 }; 386 #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " 387 388 const int nax = 2e5 + 5; 389 bool forbidden[nax]; 390 391 int my_gcd(int a, int b) { 392 if(a == 0 || b == 0) return max(a, b); // return m 393 return __gcd(a, b); 394 } 395 #define __gcd use____my_gcd 396 397 vector<int> which[nax]; 398 pair<int,int> dp[nax]; 399 400 int my_pow(int a, int b, int m) { 401 int r = 1; 402 while(b) { 403 if(b % 2) r = (long long) r * a % m; 404 a = (long long) a * a % m; 405 b /= 2; 406 } 407 return r; 408 } 409 410 int main() { 411 int n, m; 412 scanf("%d%d", &n, &m); 413 while(n--) { 414 int x; 415 scanf("%d", &x); 416 forbidden[x] = true; 417 } 418 #define n use_____m 419 for(int i = 0; i < m; ++i) 420 if(!forbidden[i]) 421 which[my_gcd(i, m)].push_back(i); 422 if(forbidden[0]) 423 which[m].push_back(0); // hack 424 for(int i = 1; i <= m; ++i) 425 if(!which[i].empty()) { 426 dp[i] = {0, 0}; 427 for(int j = 1; j < i; ++j) 428 if(i % j == 0 && dp[j].first > 0) 429 dp[i] = max(dp[i], make_pair(dp[j].first, j)); 430 dp[i].first += which[i].size(); 431 } 432 vector<int> ans; 433 int x = m; 434 while(!which[x].empty()) { 435 for(int y : which[x]) 436 ans.push_back(y); 437 x = dp[x].second; 438 } 439 reverse(ans.begin(), ans.end()); 440 if(forbidden[0]) { 441 assert(!ans.empty()); 442 ans.pop_back(); 443 } 444 debug() << imie(ans); 445 int previous = 1; 446 printf("%d\n", (int) ans.size()); 447 448 int cnt_coprime = 0; 449 for(int i = 2; i < m; ++i) 450 if(my_gcd(i, m) == 1) 451 ++cnt_coprime; 452 453 for(int nxt : ans) { 454 if(nxt == 0) { 455 printf("0"); 456 continue; 457 } 458 int a = previous / my_gcd(m, previous); 459 int b = nxt / my_gcd(m, nxt); 460 461 int print = (long long) b * my_pow(a, cnt_coprime, m) % m; 462 print = (long long) print * my_gcd(m, nxt) / my_gcd(m, previous) % m; 463 printf("%d ", print); 464 previous = nxt; 465 } 466 puts(""); 467 } 468 ``` 469 470 **example code (java)** 471 472 ``` 473 import java.io.OutputStream; 474 import java.io.IOException; 475 import java.io.InputStream; 476 import java.io.OutputStream; 477 import java.io.PrintWriter; 478 import java.util.Arrays; 479 import java.io.BufferedWriter; 480 import java.io.Writer; 481 import java.io.OutputStreamWriter; 482 import java.util.InputMismatchException; 483 import java.io.IOException; 484 import java.util.ArrayList; 485 import java.io.InputStream; 486 487 /** 488 * Built using CHelper plug-in 489 * Actual solution is at the top 490 */ 491 public class Main { 492 public static void main(String[] args) { 493 InputStream inputStream = System.in; 494 OutputStream outputStream = System.out; 495 InputReader in = new InputReader(inputStream); 496 OutputWriter out = new OutputWriter(outputStream); 497 PrefixProductSequence solver = new PrefixProductSequence(); 498 solver.solve(1, in, out); 499 out.close(); 500 } 501 502 static class PrefixProductSequence { 503 public int[] div; 504 public boolean[] forbidden; 505 public ArrayList<Long> ans; 506 public int n; 507 public int m; 508 509 public void solve(int testNumber, InputReader in, OutputWriter out) { 510 n = in.nextInt(); 511 m = in.nextInt(); 512 forbidden = new boolean[m + 1]; 513 for (int i = 0; i < n; i++) { 514 forbidden[in.nextInt()] = true; 515 } 516 int[] add = new int[m + 1]; 517 for (int i = 0; i < m; i++) { 518 if (!forbidden[i]) { 519 int g = Utils.gcd(i, m); 520 add[m / g]++; 521 } 522 } 523 int[] arr = new int[m + 1]; 524 div = new int[m + 1]; 525 Arrays.fill(arr, 1); 526 Arrays.setAll(div, x -> x); 527 for (int i = 2; i <= m; i++) { 528 arr[i] += add[i]; 529 for (int j = i + i; j <= m; j += i) { 530 if (arr[i] > arr[j]) { 531 arr[j] = arr[i]; 532 div[j] = j / i; 533 } 534 } 535 } 536 537 ans = new ArrayList<>(); 538 solve(1, 1); 539 out.println(ans.size()); 540 boolean first = true; 541 for (long x : ans) { 542 if (!first) out.print(" "); 543 out.print(x); 544 first = false; 545 } 546 out.println(); 547 } 548 549 public void solve(int cmult, long mm) { 550 if (cmult == m) { 551 if (!forbidden[0]) { 552 ans.add(0L); 553 } 554 return; 555 } 556 int prev = 1; 557 boolean has = false; 558 for (int i = 1; i < m / cmult; i++) { 559 if (!forbidden[i * cmult] && Utils.gcd(m / cmult, i) == 1) { 560 long x = Utils.inv(prev, m / cmult) * i % m; 561 if (!has) { 562 has = true; 563 x = x * mm % m; 564 } 565 ans.add(x); 566 prev = i; 567 } 568 } 569 long nmm = Utils.inv(prev, m / cmult) * div[m / cmult] % m; 570 if (!has) nmm = nmm * mm % m; 571 solve(cmult * div[m / cmult], nmm); 572 } 573 574 } 575 576 static class OutputWriter { 577 private final PrintWriter writer; 578 579 public OutputWriter(OutputStream outputStream) { 580 writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); 581 } 582 583 public OutputWriter(Writer writer) { 584 this.writer = new PrintWriter(writer); 585 } 586 587 public void print(Object... objects) { 588 for (int i = 0; i < objects.length; i++) { 589 if (i != 0) { 590 writer.print(' '); 591 } 592 writer.print(objects[i]); 593 } 594 } 595 596 public void println() { 597 writer.println(); 598 } 599 600 public void close() { 601 writer.close(); 602 } 603 604 public void print(long i) { 605 writer.print(i); 606 } 607 608 public void println(int i) { 609 writer.println(i); 610 } 611 612 } 613 614 static class InputReader { 615 private InputStream stream; 616 private byte[] buf = new byte[1024]; 617 private int curChar; 618 private int numChars; 619 620 public InputReader(InputStream stream) { 621 this.stream = stream; 622 } 623 624 public int read() { 625 if (this.numChars == -1) { 626 throw new InputMismatchException(); 627 } else { 628 if (this.curChar >= this.numChars) { 629 this.curChar = 0; 630 631 try { 632 this.numChars = this.stream.read(this.buf); 633 } catch (IOException var2) { 634 throw new InputMismatchException(); 635 } 636 637 if (this.numChars <= 0) { 638 return -1; 639 } 640 } 641 642 return this.buf[this.curChar++]; 643 } 644 } 645 646 public int nextInt() { 647 int c; 648 for (c = this.read(); isSpaceChar(c); c = this.read()) { 649 ; 650 } 651 652 byte sgn = 1; 653 if (c == 45) { 654 sgn = -1; 655 c = this.read(); 656 } 657 658 int res = 0; 659 660 while (c >= 48 && c <= 57) { 661 res *= 10; 662 res += c - 48; 663 c = this.read(); 664 if (isSpaceChar(c)) { 665 return res * sgn; 666 } 667 } 668 669 throw new InputMismatchException(); 670 } 671 672 public static boolean isSpaceChar(int c) { 673 return c == 32 || c == 10 || c == 13 || c == 9 || c == -1; 674 } 675 676 } 677 678 static class Utils { 679 public static long inv(long N, long M) { 680 long x = 0, lastx = 1, y = 1, lasty = 0, q, t, a = N, b = M; 681 while (b != 0) { 682 q = a / b; 683 t = a % b; 684 a = b; 685 b = t; 686 t = x; 687 x = lastx - q * x; 688 lastx = t; 689 t = y; 690 y = lasty - q * y; 691 lasty = t; 692 } 693 return (lastx + M) % M; 694 } 695 696 public static int gcd(int a, int b) { 697 return b == 0 ? a : gcd(b, a % b); 698 } 699 700 } 701 } 702 ``` 703 704 **Varying Kibibits** 705 706 Tutorial is loading... 707 708 **example code (c++, inclusion/exclusion approach)** 709 710 ``` 711 // vvvvvvvvvvvvvvvvv Library code start 712 713 #include <array> 714 715 #define NDEBUG 716 NDEBUG 717 718 #include <algorithm> 719 720 #include <cassert> 721 #include <cstring> 722 #include <functional> 723 #include <iomanip> 724 #include <iostream> 725 #include <map> 726 #include <set> 727 #include <sstream> 728 #include <string> 729 #include <tuple> 730 #include <unordered_map> 731 #include <unordered_set> 732 #include <vector> 733 #include <memory> 734 #include <queue> 735 #include <random> 736 737 #define forn(t, i, n) for (t i = 0; i < (n); ++i) 738 739 #define rforn(t, i, n) for (t i = (n) - 1; i >= 0; --i) 740 741 #define all(c) c.begin(), c.end() 742 743 using namespace std; 744 745 /// caide keep 746 bool __hack = std::ios::sync_with_stdio(false); 747 /// caide keep 748 auto __hack1 = cin.tie(nullptr); 749 750 // Section with adoption of array and vector algorithms. 751 752 // 32 bit ints (sum LSB + MSB == 32) 753 754 // TODO: Section with some container algorithms 755 756 #define ENABLE_IF(e) typename enable_if<e>::type* = nullptr 757 758 namespace template_util { 759 template<class T> 760 constexpr T min(T a, T b) { 761 return a < b ? a : b; 762 } 763 764 765 constexpr int bytecount(uint64_t x) { 766 return x ? 1 + bytecount(x >> 8) : 0; 767 } 768 769 /// caide keep 770 template<int N> 771 struct bytetype { 772 typedef uint64_t type; 773 }; 774 775 /// caide keep 776 template<> 777 struct bytetype<4> { 778 typedef uint32_t type; 779 }; 780 781 /// caide keep 782 template<> 783 struct bytetype<3> { 784 785 }; 786 787 /// caide keep 788 template<> 789 struct bytetype<2> { 790 791 }; 792 793 /// caide keep 794 template<> 795 struct bytetype<1> { 796 typedef uint8_t type; 797 }; 798 799 /// caide keep 800 template<> 801 struct bytetype<0> { 802 typedef uint8_t type; 803 }; 804 805 /// caide keep 806 template<uint64_t N> 807 struct minimal_uint : bytetype<bytecount(N)> { 808 }; 809 } 810 811 template<class T> 812 T next(istream& in) { 813 T ret; 814 in >> ret; 815 return ret; 816 } 817 818 template<class T> 819 vector<T> next_vector(istream& in, size_t n) { 820 vector<T> ret(n); 821 for (size_t i = 0; i < n; ++i) { 822 ret[i] = next<T>(in); 823 } 824 return ret; 825 } 826 827 #define dbg(...) ; 828 829 /* 830 TODOs: 831 cache invs 832 primitive root 833 discrete log 834 835 tests!!! 836 */ 837 838 namespace mod_impl { 839 /// caide keep 840 template <class T> 841 constexpr inline T mod(T MOD) { 842 return MOD; 843 } 844 845 /// caide keep 846 template <class T> 847 constexpr inline T mod(T* MOD) { 848 return *MOD; 849 } 850 851 /// caide keep 852 template <class T> 853 constexpr inline T max_mod(T MOD) { 854 return MOD - 1; 855 } 856 857 /// caide keep 858 template <class T> 859 constexpr inline T max_mod(T*) { 860 return numeric_limits<T>::max() - 1; 861 } 862 863 864 constexpr inline uint64_t combine_max_sum(uint64_t a, uint64_t b) { 865 return a > ~b ? 0 : a + b; 866 } 867 868 constexpr inline uint64_t combine_max_mul(uint64_t a, uint64_t b) { 869 return a > numeric_limits<uint64_t>::max() / b ? 0 : a * b; 870 } 871 872 /// caide keep 873 template <class T> 874 constexpr inline uint64_t next_divisible(T mod, uint64_t max) { 875 return max % mod == 0 ? max : combine_max_sum(max, mod - max % mod); 876 } 877 878 /// caide keep 879 template <class T> 880 constexpr inline uint64_t next_divisible(T*, uint64_t) { 881 return 0; 882 } 883 884 //caide keep 885 constexpr int IF_THRESHOLD = 2; 886 887 template <class T, T MOD_VALUE, uint64_t MAX, 888 class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type, 889 ENABLE_IF(MAX <= max_mod(MOD_VALUE) && !is_pointer<T>::value)> 890 inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) { 891 return value; 892 } 893 894 template <class T, T MOD_VALUE, uint64_t MAX, 895 class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type, 896 ENABLE_IF(max_mod(MOD_VALUE) < MAX && MAX <= IF_THRESHOLD * max_mod(MOD_VALUE) && !is_pointer<T>::value)> 897 inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) { 898 while (value >= mod(MOD_VALUE)) { 899 value -= mod(MOD_VALUE); 900 } 901 return (RET)value; 902 } 903 904 template <class T, T MOD_VALUE, uint64_t MAX, 905 class RET = typename template_util::minimal_uint<max_mod(MOD_VALUE)>::type, 906 ENABLE_IF(IF_THRESHOLD * max_mod(MOD_VALUE) < MAX || is_pointer<T>::value)> 907 inline RET smart_mod(typename template_util::minimal_uint<MAX>::type value) { 908 return (RET)(value % mod(MOD_VALUE)); 909 } 910 } 911 912 #define MOD mod_impl::mod(MOD_VALUE) 913 #define MAX_MOD mod_impl::max_mod(MOD_VALUE) 914 915 struct DenormTag {}; 916 917 template <class T, T MOD_VALUE, uint64_t MAX = MAX_MOD, ENABLE_IF(MAX_MOD >= 2)> 918 struct ModVal { 919 typedef typename template_util::minimal_uint<MAX>::type storage; 920 storage value; 921 922 /// caide keep 923 inline ModVal(): value(0) { 924 assert(MOD >= 2); 925 } 926 927 928 inline ModVal(storage v, DenormTag): value(v) { 929 assert(MOD >= 2); 930 assert(v <= MAX); 931 }; 932 933 inline operator ModVal<T, MOD_VALUE>() { 934 return {v(), DenormTag()}; 935 }; 936 937 explicit inline operator uint64_t() const { 938 return v(); 939 } 940 941 typename template_util::minimal_uint<mod_impl::max_mod(MOD_VALUE)>::type v() const { 942 return mod_impl::smart_mod<T, MOD_VALUE, MAX>(value); 943 } 944 }; 945 946 template <class T, T MOD_VALUE, uint64_t MAX, 947 uint64_t NEW_MAX = mod_impl::next_divisible(MOD_VALUE, MAX), 948 ENABLE_IF(NEW_MAX != 0), 949 class Ret = ModVal<T, MOD_VALUE, NEW_MAX>> 950 inline Ret operator-(const ModVal<T, MOD_VALUE, MAX>& o) { 951 static_assert(NEW_MAX <= numeric_limits<typename Ret::storage>::max(), "bad unary minus template"); 952 assert(NEW_MAX % MOD == 0 && o.value <= NEW_MAX); 953 return {typename Ret::storage(NEW_MAX - o.value), DenormTag()}; 954 } 955 956 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2, 957 uint64_t NEW_MAX = mod_impl::combine_max_sum(MAX1, MAX2), 958 ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>> 959 inline Ret operator+(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) { 960 return {typename Ret::storage(typename Ret::storage() + o1.value + o2.value), DenormTag()}; 961 } 962 963 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2, 964 uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2), 965 ENABLE_IF(NEW_MAX != 0), class Ret = ModVal<T, MOD_VALUE, NEW_MAX>> 966 inline Ret operator*(ModVal<T, MOD_VALUE, MAX1> o1, ModVal<T, MOD_VALUE, MAX2> o2) { 967 return {typename Ret::storage(typename Ret::storage(1) * o1.value * o2.value), DenormTag()}; 968 } 969 970 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2, 971 uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2), 972 uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)), 973 ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 != 0 && MAX1 <= MAX2), 974 class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX1, MAX_MOD)>> 975 inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) { 976 return {typename Ret::storage(typename Ret::storage(1) * o1.value * o2.v()), DenormTag()}; 977 } 978 979 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2, 980 uint64_t NEW_MAX = mod_impl::combine_max_mul(MAX1, MAX2), 981 uint64_t NEW_MAX1 = mod_impl::combine_max_mul(MAX_MOD, template_util::min(MAX1, MAX2)), 982 ENABLE_IF(NEW_MAX == 0 && NEW_MAX1 != 0 && MAX2 < MAX1), 983 class Ret = ModVal<T, MOD_VALUE, mod_impl::combine_max_mul(MAX_MOD, MAX2)>> 984 inline Ret operator*(const ModVal<T, MOD_VALUE, MAX1>& o1, const ModVal<T, MOD_VALUE, MAX2>& o2) { 985 return {typename Ret::storage(typename Ret::storage(1) * o1.v() * o2.value), DenormTag()}; 986 } 987 988 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2> 989 inline auto operator-(const ModVal<T, MOD_VALUE, MAX1>& lhs, const ModVal<T, MOD_VALUE, MAX2>& rhs) -> decltype(lhs + (-rhs)) { 990 return lhs + (-rhs); 991 } 992 993 template <class T, T MOD_VALUE, uint64_t MAX> 994 inline ModVal<T, MOD_VALUE>& operator+=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) { 995 lhs = lhs + rhs; 996 return lhs; 997 } 998 999 template <class T, T MOD_VALUE, uint64_t MAX> 1000 inline ModVal<T, MOD_VALUE>& operator-=(ModVal<T, MOD_VALUE>& lhs, const ModVal<T, MOD_VALUE, MAX>& rhs) { 1001 lhs = lhs - rhs; 1002 return lhs; 1003 } 1004 1005 template <class T, T MOD_VALUE, uint64_t MAX1, uint64_t MAX2> 1006 inline bool operator!=(const ModVal<T, MOD_VALUE, MAX1>& lhs, const ModVal<T, MOD_VALUE, MAX2>& rhs) { 1007 return lhs.v() != rhs.v(); 1008 } 1009 1010 template <class T, T MOD_VALUE, class MOD_TYPE> 1011 struct ModCompanion { 1012 typedef MOD_TYPE mod_type; 1013 typedef ModVal<mod_type, MOD_VALUE> type; 1014 1015 1016 template <uint64_t C> 1017 inline static constexpr ModVal<mod_type, MOD_VALUE, C> c() { 1018 return {C, DenormTag()}; 1019 }; 1020 1021 template <uint64_t MAX = numeric_limits<uint64_t>::max()> 1022 inline static ModVal<mod_type, MOD_VALUE, MAX> wrap(uint64_t x) { 1023 assert(x <= MAX); 1024 return {typename ModVal<mod_type, MOD_VALUE, MAX>::storage(x), DenormTag()}; 1025 }; 1026 1027 template <uint64_t MAX, ENABLE_IF(!is_pointer<T>::value && MAX <= MAX_MOD)> 1028 inline static ModVal<mod_type, MOD_VALUE> inv(const ModVal<mod_type, MOD_VALUE, MAX>& x) { 1029 if (x.value == 1) { 1030 return c<1>(); 1031 } 1032 return -(wrap<MAX_MOD / 2>(MOD / x.value) * inv(wrap<MAX>(MOD % x.value))); 1033 }; 1034 1035 1036 }; 1037 1038 #undef MOD 1039 #undef MAX_MOD 1040 1041 template <uint64_t MOD_VALUE> 1042 struct Mod : ModCompanion<uint64_t, MOD_VALUE, typename template_util::minimal_uint<MOD_VALUE>::type> { 1043 template<uint64_t VAL> 1044 static constexpr uint64_t literal_builder() { 1045 return VAL; 1046 } 1047 1048 template<uint64_t VAL, char DIGIT, char... REST> 1049 static constexpr uint64_t literal_builder() { 1050 return literal_builder<(10 * VAL + DIGIT - '0') % MOD_VALUE, REST...>(); 1051 } 1052 }; 1053 1054 #define REGISTER_MOD_LITERAL(mod, suffix) \ 1055 template <char... DIGITS> mod::type operator "" _##suffix() { \ 1056 return mod::c<mod::literal_builder<0, DIGITS...>()>(); \ 1057 } 1058 1059 // ^^^^^^^^^^^^^^^^^ Library code end 1060 1061 using md = Mod<1000000007>; 1062 using mt = md::type; 1063 REGISTER_MOD_LITERAL(md, mod) 1064 1065 using Val = tuple<int, mt, mt>; 1066 1067 mt pow2s[1000001], powInv2s[1000001]; 1068 1069 mt pow2(int p) { 1070 return p < 0 ? powInv2s[-p] : pow2s[p]; 1071 } 1072 1073 Val mul(Val a, Val b) { 1074 const mt p2a = pow2(get<0>(a)); 1075 const mt p2b = pow2(get<0>(b)); 1076 return Val{get<0>(a) + get<0>(b), p2a * get<1>(b) + get<1>(a) * p2b, p2a * get<2>(b) + 2_mod * get<1>(a) * get<1>(b) + get<2>(a) * p2b}; 1077 } 1078 1079 Val inv(Val a) { 1080 Val b; 1081 get<0>(b) = -get<0>(a); 1082 const mt p2b = pow2(get<0>(b)); 1083 get<1>(b) = -p2b * (get<1>(a) * p2b); 1084 get<2>(b) = -p2b * (2_mod * get<1>(a) * get<1>(b) + get<2>(a) * p2b); 1085 return b; 1086 } 1087 1088 Val d[1000000][7]; 1089 mt dSum[1000000][7]; 1090 1091 void solve(istream& in, ostream& out) { 1092 pow2s[0] = powInv2s[0] = 1_mod; 1093 mt inv2 = md::inv(2_mod); 1094 forn (int, i, 1000000) { 1095 pow2s[i + 1] = pow2s[i] * 2_mod; 1096 powInv2s[i + 1] = powInv2s[i] * inv2; 1097 } 1098 1099 int n = next<int>(in); 1100 auto as = next_vector<int>(in, n); 1101 sort(all(as)); 1102 uint64_t ans = 0; 1103 int add[1 << 6]; 1104 forn (int, mask, 1 << 6) { 1105 add[mask] = 0; 1106 int mask1 = mask; 1107 forn (int, it, 6) { 1108 add[mask] = add[mask] * 10 + (mask1 & 1); 1109 mask1 /= 2; 1110 } 1111 } 1112 int asIt = n - 1; 1113 rforn (int, x, 1000000) { 1114 int badMask = 0; 1115 int x1 = x; 1116 forn (int, it, 6) { 1117 badMask = 2 * badMask + (x1 % 10 == 9 ? 1 : 0); 1118 x1 /= 10; 1119 } 1120 d[x][0] = Val{0, 0_mod, 0_mod}; 1121 dSum[x][0] = 0_mod; 1122 forn (int, bit, 6) { 1123 d[x][bit + 1] = d[x][bit]; 1124 dSum[x][bit + 1] = dSum[x][bit]; 1125 if (!(badMask & (1 << bit))) { 1126 d[x][bit + 1] = mul(d[x][bit + 1], inv(d[x + add[1 << bit]][bit])); 1127 dSum[x][bit + 1] -= dSum[x + add[1 << bit]][bit]; 1128 } 1129 } 1130 auto val = inv(d[x][6]); 1131 while (asIt >= 0 && as[asIt] == x) { 1132 --asIt; 1133 val = mul(val, Val{1, md::wrap(x), md::wrap(1ULL * x * x)}); 1134 } 1135 auto sum = get<2>(val) + dSum[x][6]; 1136 forn (int, bit, 6) { 1137 d[x][bit] = mul(d[x][bit], val); 1138 dSum[x][bit] += get<2>(val); 1139 } 1140 if (sum != 0_mod) { 1141 dbg(x, sum, x * uint64_t(sum)); 1142 ans ^= x * uint64_t(sum); 1143 } 1144 } 1145 out << ans << endl; 1146 } 1147 1148 int main() { 1149 solve(cin, cout); 1150 return 0; 1151 } 1152 ``` 1153 1154 **example code (java, FWHT approach)** 1155 1156 ``` 1157 import java.io.OutputStream; 1158 import java.io.IOException; 1159 import java.io.InputStream; 1160 import java.io.OutputStream; 1161 import java.io.PrintWriter; 1162 import java.io.BufferedWriter; 1163 import java.io.Writer; 1164 import java.io.OutputStreamWriter; 1165 import java.util.InputMismatchException; 1166 import java.io.IOException; 1167 import java.io.InputStream; 1168 1169 /** 1170 * Built using CHelper plug-in 1171 * Actual solution is at the top 1172 */ 1173 public class Main { 1174 public static void main(String[] args) { 1175 InputStream inputStream = System.in; 1176 OutputStream outputStream = System.out; 1177 InputReader in = new InputReader(inputStream); 1178 OutputWriter out = new OutputWriter(outputStream); 1179 MinAddition solver = new MinAddition(); 1180 solver.solve(1, in, out); 1181 out.close(); 1182 } 1183 1184 static class MinAddition { 1185 public int[] pow10 = {1, 10, 100, 1000, 10000, 100000, 1000000}; 1186 public int MAXN = 1000000; 1187 public int LOG = 6; 1188 public int mod = 1000000007; 1189 1190 public void solve(int testNumber, InputReader in, OutputWriter out) { 1191 int n = in.nextInt(); 1192 int[] freq = new int[MAXN]; 1193 int[] sum = new int[MAXN]; 1194 int[] sum2 = new int[MAXN]; 1195 int[] pow2 = new int[n + 1]; 1196 pow2[0] = 1; 1197 for (int i = 1; i <= n; i++) pow2[i] = (pow2[i - 1] << 1) % mod; 1198 for (int i = 0; i < n; i++) { 1199 int a = in.nextInt(); 1200 freq[a]++; 1201 sum[a] += a; 1202 if (sum[a] >= mod) sum[a] -= mod; 1203 int x = (int) (1L * a * a % mod); 1204 sum2[a] += x; 1205 if (sum2[a] >= mod) sum2[a] -= mod; 1206 } 1207 1208 int[] mod10 = new int[MAXN]; 1209 for (int i = 0; i < 10; i++) mod10[i] = i; 1210 for (int i = 10; i < MAXN; i++) mod10[i] = mod10[i - 10]; 1211 1212 for (int level = LOG - 1; level >= 0; level--) { 1213 for (int i = MAXN - 1; i >= 0; i--) { 1214 int d = mod10[i / pow10[level]]; 1215 if (d > 0) { 1216 int p = i - pow10[level]; 1217 freq[p] += freq[i]; 1218 sum[p] += sum[i]; 1219 if (sum[p] >= mod) sum[p] -= mod; 1220 sum2[p] += sum2[i]; 1221 if (sum2[p] >= mod) sum2[p] -= mod; 1222 } 1223 } 1224 } 1225 for (int i = 0; i < MAXN; i++) { 1226 int sdiff = (int) ((1L * sum[i] * sum[i] + mod - sum2[i]) % mod); 1227 int ssame = sum2[i]; 1228 int g = 0; 1229 if (freq[i] >= 1) 1230 g += (int) (1L * ssame * pow2[freq[i] - 1] % mod); 1231 if (freq[i] >= 2) 1232 g += (int) (1L * sdiff * pow2[freq[i] - 2] % mod); 1233 while (g >= mod) g -= mod; 1234 freq[i] = g; 1235 } 1236 1237 for (int level = 0; level < LOG; level++) { 1238 for (int i = 0; i < MAXN; i++) { 1239 int d = mod10[i / pow10[level]]; 1240 if (d + 1 < 10) { 1241 int p = i + pow10[level]; 1242 freq[i] -= freq[p]; 1243 if (freq[i] < 0) freq[i] += mod; 1244 } 1245 } 1246 } 1247 1248 long s = 0; 1249 for (int i = 0; i < MAXN; i++) { 1250 s ^= 1L * i * freq[i]; 1251 } 1252 out.println(s); 1253 } 1254 1255 } 1256 1257 static class OutputWriter { 1258 private final PrintWriter writer; 1259 1260 public OutputWriter(OutputStream outputStream) { 1261 writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); 1262 } 1263 1264 public OutputWriter(Writer writer) { 1265 this.writer = new PrintWriter(writer); 1266 } 1267 1268 public void close() { 1269 writer.close(); 1270 } 1271 1272 public void println(long i) { 1273 writer.println(i); 1274 } 1275 1276 } 1277 1278 static class InputReader { 1279 private InputStream stream; 1280 private byte[] buf = new byte[1024]; 1281 private int curChar; 1282 private int numChars; 1283 1284 public InputReader(InputStream stream) { 1285 this.stream = stream; 1286 } 1287 1288 public int read() { 1289 if (this.numChars == -1) { 1290 throw new InputMismatchException(); 1291 } else { 1292 if (this.curChar >= this.numChars) { 1293 this.curChar = 0; 1294 1295 try { 1296 this.numChars = this.stream.read(this.buf); 1297 } catch (IOException var2) { 1298 throw new InputMismatchException(); 1299 } 1300 1301 if (this.numChars <= 0) { 1302 return -1; 1303 } 1304 } 1305 1306 return this.buf[this.curChar++]; 1307 } 1308 } 1309 1310 public int nextInt() { 1311 int c; 1312 for (c = this.read(); isSpaceChar(c); c = this.read()) { 1313 ; 1314 } 1315 1316 byte sgn = 1; 1317 if (c == 45) { 1318 sgn = -1; 1319 c = this.read(); 1320 } 1321 1322 int res = 0; 1323 1324 while (c >= 48 && c <= 57) { 1325 res *= 10; 1326 res += c - 48; 1327 c = this.read(); 1328 if (isSpaceChar(c)) { 1329 return res * sgn; 1330 } 1331 } 1332 1333 throw new InputMismatchException(); 1334 } 1335 1336 public static boolean isSpaceChar(int c) { 1337 return c == 32 || c == 10 || c == 13 || c == 9 || c == -1; 1338 } 1339 1340 } 1341 } 1342 ``` 1343 1344 **Verifying Kingdom** 1345 1346 Tutorial is loading... 1347 1348 **example code (c++)** 1349 1350 ``` 1351 // vvvvvvvvvvvvvvvvv Library code start 1352 1353 #define NDEBUG 1354 NDEBUG 1355 1356 #include <algorithm> 1357 #include <array> 1358 #include <cassert> 1359 #include <cstring> 1360 #include <functional> 1361 #include <iomanip> 1362 #include <iostream> 1363 #include <map> 1364 #include <set> 1365 #include <sstream> 1366 #include <string> 1367 #include <tuple> 1368 #include <unordered_map> 1369 #include <unordered_set> 1370 #include <vector> 1371 #include <memory> 1372 #include <queue> 1373 #include <random> 1374 1375 #define forn(t, i, n) for (t i = 0; i < (n); ++i) 1376 #define foran(t, i, a, n) for (t i = (a); i < (n); ++i) 1377 1378 using namespace std; 1379 1380 /// caide keep 1381 bool __hack = std::ios::sync_with_stdio(false); 1382 /// caide keep 1383 auto __hack1 = cin.tie(nullptr); 1384 1385 template<class T> 1386 inline T mn(T arg) { 1387 return arg; 1388 } 1389 1390 template<class T, class... Args> 1391 inline bool rmx(T &to, Args... args) { 1392 auto v = mn(args...); 1393 if (to < v) { 1394 to = v; 1395 return true; 1396 } 1397 return false; 1398 } 1399 1400 // Section with adoption of array and vector algorithms. 1401 1402 // 32 bit ints (sum LSB + MSB == 32) 1403 1404 // TODO: Section with some container algorithms 1405 1406 namespace template_util { 1407 1408 1409 constexpr int bytecount(uint64_t x) { 1410 return x ? 1 + bytecount(x >> 8) : 0; 1411 } 1412 1413 /// caide keep 1414 template<int N> 1415 struct bytetype { 1416 1417 }; 1418 1419 /// caide keep 1420 template<> 1421 struct bytetype<4> { 1422 1423 }; 1424 1425 /// caide keep 1426 template<> 1427 struct bytetype<3> { 1428 1429 }; 1430 1431 /// caide keep 1432 template<> 1433 struct bytetype<2> { 1434 1435 }; 1436 1437 /// caide keep 1438 template<> 1439 struct bytetype<1> { 1440 1441 }; 1442 1443 /// caide keep 1444 template<> 1445 struct bytetype<0> { 1446 1447 }; 1448 1449 /// caide keep 1450 template<uint64_t N> 1451 struct minimal_uint : bytetype<bytecount(N)> { 1452 }; 1453 } 1454 1455 template<class T> 1456 T next(istream& in) { 1457 T ret; 1458 in >> ret; 1459 return ret; 1460 } 1461 1462 // ^^^^^^^^^^^^^^^^^ Library code end 1463 1464 int tr[1000][3]; 1465 int l[1000], r[1000]; 1466 bool col[1000]; 1467 int ans[2000]; 1468 1469 tuple<int, int, int> chooseDfs(int total, int i, int p = -1) { 1470 int size = 1, best = -1, bestSize = 1000000000, maxSize = 0; 1471 forn (int, e, 3) { 1472 int j = tr[i][e]; 1473 if (j != p && j >= 0 && !col[j]) { 1474 auto r1 = chooseDfs(total, j, i); 1475 if (get<1>(r1) < bestSize) { 1476 best = get<0>(r1); 1477 bestSize = get<1>(r1); 1478 } 1479 size += get<2>(r1); 1480 rmx(maxSize, get<2>(r1)); 1481 } 1482 } 1483 rmx(maxSize, total - size); 1484 if (maxSize < bestSize) { 1485 best = i; 1486 bestSize = maxSize; 1487 } 1488 return tuple<int, int, int>{best, bestSize, size}; 1489 } 1490 1491 int sizeDfs(int i, int p = -1) { 1492 auto r = 1; 1493 forn (int, e, 3) { 1494 int j = tr[i][e]; 1495 if (j != p && j >= 0 && !col[j]) { 1496 r += sizeDfs(j, i); 1497 } 1498 } 1499 return r; 1500 } 1501 1502 void ansDfs(int n, int i) { 1503 forn (int, e, 2) { 1504 if (tr[i][e] >= 0) { 1505 ansDfs(n, tr[i][e]); 1506 } 1507 ans[tr[i][e] < 0 ? -2 - tr[i][e] : n + tr[i][e]] = n + i + 1; 1508 } 1509 } 1510 1511 void solve(istream& in, ostream& out) { 1512 auto q = [&](int a, int b, int c) { 1513 out << a + 1 << " " << b + 1 << " " << c + 1 << endl; 1514 string s = next<string>(in); 1515 if (s == "X") { 1516 return 2; 1517 } else if (s == "Y") { 1518 return 1; 1519 } else if (s == "Z") { 1520 return 0; 1521 } else { 1522 throw 42; 1523 } 1524 }; 1525 int n = next<int>(in); 1526 memset(tr, -1, sizeof(tr)); 1527 tr[0][0] = -2; 1528 tr[0][1] = -3; 1529 l[0] = 0; 1530 r[0] = 1; 1531 foran (int, i, 2, n) { 1532 memset(col, 0, sizeof(col)); 1533 int x = 0; 1534 while (true) { 1535 x = get<0>(chooseDfs(sizeDfs(x), x)); 1536 int e = q(l[x], r[x], i); 1537 if (tr[x][e] < 0 || col[tr[x][e]]) { 1538 if (tr[x][e] >= 0) { 1539 forn (int, e1, 3) { 1540 if (tr[tr[x][e]][e1] == x) { 1541 tr[tr[x][e]][e1] = i - 1; 1542 } 1543 } 1544 } 1545 tr[i - 1][e] = tr[x][e]; 1546 tr[x][e] = i - 1; 1547 tr[i - 1][e == 0 ? 1 : 0] = -2 - i; 1548 tr[i - 1][e == 2 ? 1 : 2] = x; 1549 l[i - 1] = tr[i - 1][0] < 0 ? -2 - tr[i - 1][0] : l[tr[i - 1][0]]; 1550 r[i - 1] = tr[i - 1][1] < 0 ? -2 - tr[i - 1][1] : r[tr[i - 1][1]]; 1551 break; 1552 } 1553 col[x] = true; 1554 x = tr[x][e]; 1555 } 1556 } 1557 int r = 0; 1558 while (tr[r][2] != -1) { 1559 r = tr[r][2]; 1560 } 1561 ans[n + r] = -1; 1562 ansDfs(n, r); 1563 out << "-1\n"; 1564 forn (int, i, 2 * n - 1) { 1565 out << ans[i] << " "; 1566 } 1567 out << "\n"; 1568 } 1569 1570 int main() { 1571 solve(cin, cout); 1572 return 0; 1573 } 1574 ``` 1575 1576 **example code (java)** 1577 1578 ``` 1579 import java.io.OutputStream; 1580 import java.io.IOException; 1581 import java.io.InputStream; 1582 import java.io.OutputStream; 1583 import java.io.PrintWriter; 1584 import java.io.BufferedWriter; 1585 import java.io.Writer; 1586 import java.io.OutputStreamWriter; 1587 import java.util.InputMismatchException; 1588 import java.io.IOException; 1589 import java.io.InputStream; 1590 1591 /** 1592 * Built using CHelper plug-in 1593 * Actual solution is at the top 1594 */ 1595 public class Main { 1596 public static void main(String[] args) { 1597 InputStream inputStream = System.in; 1598 OutputStream outputStream = System.out; 1599 InputReader in = new InputReader(inputStream); 1600 OutputWriter out = new OutputWriter(outputStream); 1601 ForgottenTree solver = new ForgottenTree(); 1602 solver.solve(1, in, out); 1603 out.close(); 1604 } 1605 1606 static class ForgottenTree { 1607 public InputReader in; 1608 public OutputWriter out; 1609 public int nidx; 1610 public int n; 1611 public int[] par; 1612 1613 public void solve(int testNumber, InputReader in, OutputWriter out) { 1614 this.in = in; 1615 this.out = out; 1616 1617 n = in.nextInt(); 1618 nidx = n; 1619 ForgottenTree.Node root = new ForgottenTree.Node(0); 1620 ForgottenTree.Node.cgen = 0; 1621 for (int i = 1; i < n; i++) { 1622 ForgottenTree.Node.cgen++; 1623 root.getLeaves(); 1624 root = insert(root, i); 1625 } 1626 out.println(-1); 1627 par = new int[2 * n - 1]; 1628 dfs(root, -2); 1629 out.println(par); 1630 } 1631 1632 public String ask(int a, int b, int c) { 1633 out.println((a + 1) + " " + (b + 1) + " " + (c + 1)); 1634 out.flush(); 1635 String ret = in.next(); 1636 if (ret.equals("-1")) System.exit(0); 1637 return ret; 1638 } 1639 1640 public void dfs(ForgottenTree.Node root, int p) { 1641 par[root.label] = p + 1; 1642 if (root.lchild != null) { 1643 dfs(root.lchild, root.label); 1644 dfs(root.rchild, root.label); 1645 } 1646 } 1647 1648 public ForgottenTree.Node insert(ForgottenTree.Node root, int label) { 1649 if (!root.active()) { 1650 return add(root, label); 1651 } 1652 root.dfs(); 1653 1654 if (root.lchild == null) { 1655 return add(root, label); 1656 } 1657 1658 int curleaves = root.nleaves; 1659 if (curleaves <= 1) { 1660 int nnodes = 0; 1661 ForgottenTree.Node cur = root; 1662 while (!cur.isLeaf()) { 1663 nnodes++; 1664 if (cur.lchild.active()) cur = cur.lchild; 1665 else cur = cur.rchild; 1666 } 1667 cur = root; 1668 int depth = 0; 1669 while (2 * (depth + 1) < nnodes) { 1670 if (cur.lchild.active()) cur = cur.lchild; 1671 else cur = cur.rchild; 1672 depth++; 1673 } 1674 1675 return process(root, cur, label); 1676 } 1677 1678 ForgottenTree.Node cur = root; 1679 while (true) { 1680 if (cur.lchild == null) { 1681 if (cur.par == null) { 1682 return add(cur, label); 1683 } 1684 if (cur.which == 0) { 1685 cur.par.setChild(0, add(cur, label)); 1686 return root; 1687 } else { 1688 cur.par.setChild(1, add(cur, label)); 1689 return root; 1690 } 1691 } 1692 int x1 = cur.lchild.active() ? cur.lchild.nleaves : 0; 1693 int x2 = cur.rchild.active() ? cur.rchild.nleaves : 0; 1694 1695 if (x1 * 2 > curleaves) { 1696 cur = cur.lchild; 1697 continue; 1698 } 1699 if (x2 * 2 > curleaves) { 1700 cur = cur.rchild; 1701 continue; 1702 } 1703 1704 return process(root, cur, label); 1705 } 1706 } 1707 1708 public ForgottenTree.Node process(ForgottenTree.Node root, ForgottenTree.Node cur, int label) { 1709 String s = ask(cur.x, cur.y, label); 1710 switch (s) { 1711 case "X": 1712 if (cur.par == null) { 1713 return add(cur, label); 1714 } 1715 cur.disable(); 1716 return insert(root, label); 1717 case "Y": 1718 cur.setChild(1, insert(cur.rchild, label)); 1719 return root; 1720 case "Z": 1721 cur.setChild(0, insert(cur.lchild, label)); 1722 return root; 1723 default: 1724 throw new RuntimeException(); 1725 } 1726 } 1727 1728 public ForgottenTree.Node add(ForgottenTree.Node cnode, int label) { 1729 ForgottenTree.Node add = new ForgottenTree.Node(nidx++); 1730 add.setChild(0, cnode); 1731 add.setChild(1, new ForgottenTree.Node(label)); 1732 return add; 1733 } 1734 1735 static class Node { 1736 public static int cgen; 1737 public int x; 1738 public int y; 1739 public int label; 1740 public int gen; 1741 public int nleaves; 1742 public int which; 1743 public ForgottenTree.Node lchild; 1744 public ForgottenTree.Node rchild; 1745 public ForgottenTree.Node par; 1746 1747 public Node(int label) { 1748 this.lchild = null; 1749 this.rchild = null; 1750 this.par = null; 1751 this.which = 0; 1752 this.label = label; 1753 this.gen = 0; 1754 this.nleaves = 1; 1755 } 1756 1757 public boolean active() { 1758 return gen < cgen; 1759 } 1760 1761 public void disable() { 1762 this.gen = cgen; 1763 } 1764 1765 public boolean isLeaf() { 1766 return lchild == null || (!lchild.active() && !rchild.active()); 1767 } 1768 1769 public void setChild(int which, ForgottenTree.Node x) { 1770 if (which == 0) { 1771 this.lchild = x; 1772 } else { 1773 this.rchild = x; 1774 } 1775 x.par = this; 1776 x.which = which; 1777 } 1778 1779 public void dfs() { 1780 if (isLeaf()) { 1781 this.nleaves = 1; 1782 return; 1783 } 1784 1785 this.nleaves = 0; 1786 if (lchild.active()) { 1787 lchild.dfs(); 1788 this.nleaves += lchild.nleaves; 1789 } 1790 if (rchild.active()) { 1791 rchild.dfs(); 1792 this.nleaves += rchild.nleaves; 1793 } 1794 } 1795 1796 public void getLeaves() { 1797 if (lchild == null) { 1798 this.x = this.y = label; 1799 return; 1800 } 1801 lchild.getLeaves(); 1802 rchild.getLeaves(); 1803 this.x = lchild.x; 1804 this.y = rchild.x; 1805 } 1806 1807 } 1808 1809 } 1810 1811 static class InputReader { 1812 private InputStream stream; 1813 private byte[] buf = new byte[1024]; 1814 private int curChar; 1815 private int numChars; 1816 1817 public InputReader(InputStream stream) { 1818 this.stream = stream; 1819 } 1820 1821 public int read() { 1822 if (this.numChars == -1) { 1823 throw new InputMismatchException(); 1824 } else { 1825 if (this.curChar >= this.numChars) { 1826 this.curChar = 0; 1827 1828 try { 1829 this.numChars = this.stream.read(this.buf); 1830 } catch (IOException var2) { 1831 throw new InputMismatchException(); 1832 } 1833 1834 if (this.numChars <= 0) { 1835 return -1; 1836 } 1837 } 1838 1839 return this.buf[this.curChar++]; 1840 } 1841 } 1842 1843 public int nextInt() { 1844 int c; 1845 for (c = this.read(); isSpaceChar(c); c = this.read()) { 1846 ; 1847 } 1848 1849 byte sgn = 1; 1850 if (c == 45) { 1851 sgn = -1; 1852 c = this.read(); 1853 } 1854 1855 int res = 0; 1856 1857 while (c >= 48 && c <= 57) { 1858 res *= 10; 1859 res += c - 48; 1860 c = this.read(); 1861 if (isSpaceChar(c)) { 1862 return res * sgn; 1863 } 1864 } 1865 1866 throw new InputMismatchException(); 1867 } 1868 1869 public String next() { 1870 int c; 1871 while (isSpaceChar(c = this.read())) { 1872 ; 1873 } 1874 1875 StringBuilder result = new StringBuilder(); 1876 result.appendCodePoint(c); 1877 1878 while (!isSpaceChar(c = this.read())) { 1879 result.appendCodePoint(c); 1880 } 1881 1882 return result.toString(); 1883 } 1884 1885 public static boolean isSpaceChar(int c) { 1886 return c == 32 || c == 10 || c == 13 || c == 9 || c == -1; 1887 } 1888 1889 } 1890 1891 static class OutputWriter { 1892 private final PrintWriter writer; 1893 1894 public OutputWriter(OutputStream outputStream) { 1895 writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream))); 1896 } 1897 1898 public OutputWriter(Writer writer) { 1899 this.writer = new PrintWriter(writer); 1900 } 1901 1902 public void print(Object... objects) { 1903 for (int i = 0; i < objects.length; i++) { 1904 if (i != 0) { 1905 writer.print(' '); 1906 } 1907 writer.print(objects[i]); 1908 } 1909 } 1910 1911 public void print(int[] array) { 1912 for (int i = 0; i < array.length; i++) { 1913 if (i != 0) { 1914 writer.print(' '); 1915 } 1916 writer.print(array[i]); 1917 } 1918 } 1919 1920 public void println(int[] array) { 1921 print(array); 1922 writer.println(); 1923 } 1924 1925 public void println(Object... objects) { 1926 print(objects); 1927 writer.println(); 1928 } 1929 1930 public void close() { 1931 writer.close(); 1932 } 1933 1934 public void flush() { 1935 writer.flush(); 1936 } 1937 1938 public void println(int i) { 1939 writer.println(i); 1940 } 1941 1942 } 1943 } 1944 ```