Submission #993971

#	Time	Username	Problem	Language	Result	Execution time	Memory
993971		ThegeekKnight16	Painting Squares (IOI20_squares)	C++17	100 / 100	62 ms	776 KiB

squares

#include "squares.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
vector<int> path = {0, 1, 2, 4, 8, 16, 32, 64, 128, 256, 513, 3, 6, 12, 24, 48, 96, 192, 384, 769, 514, 5, 10, 20, 40, 80, 160, 320, 640, 257, 515, 7, 14, 28, 56, 112, 224, 448, 897, 770, 516, 9, 18, 36, 72, 144, 288, 576, 129, 258, 517, 11, 22, 44, 88, 176, 352, 704, 385, 771, 518, 13, 26, 52, 104, 208, 416, 832, 641, 259, 519, 15, 30, 60, 120, 240, 480, 961, 898, 772, 520, 17, 34, 68, 136, 272, 544, 65, 130, 260, 521, 19, 38, 76, 152, 304, 608, 193, 386, 773, 522, 21, 42, 84, 168, 336, 672, 321, 642, 261, 523, 23, 46, 92, 184, 368, 736, 449, 899, 774, 524, 25, 50, 100, 200, 400, 800, 577, 131, 262, 525, 27, 54, 108, 216, 432, 864, 705, 387, 775, 526, 29, 58, 116, 232, 464, 928, 833, 643, 263, 527, 31, 62, 124, 248, 496, 993, 962, 900, 776, 528, 33, 66, 132, 264, 529, 35, 70, 140, 280, 560, 97, 194, 388, 777, 530, 37, 74, 148, 296, 592, 161, 322, 644, 265, 531, 39, 78, 156, 312, 624, 225, 450, 901, 778, 532, 41, 82, 164, 328, 656, 289, 578, 133, 266, 533, 43, 86, 172, 344, 688, 353, 706, 389, 779, 534, 45, 90, 180, 360, 720, 417, 834, 645, 267, 535, 47, 94, 188, 376, 752, 481, 963, 902, 780, 536, 49, 98, 196, 392, 784, 545, 67, 134, 268, 537, 51, 102, 204, 408, 816, 609, 195, 390, 781, 538, 53, 106, 212, 424, 848, 673, 323, 646, 269, 539, 55, 110, 220, 440, 880, 737, 451, 903, 782, 540, 57, 114, 228, 456, 912, 801, 579, 135, 270, 541, 59, 118, 236, 472, 944, 865, 707, 391, 783, 542, 61, 122, 244, 488, 976, 929, 835, 647, 271, 543, 63, 126, 252, 504, 1009, 994, 964, 904, 785, 546, 69, 138, 276, 552, 81, 162, 324, 648, 273, 547, 71, 142, 284, 568, 113, 226, 452, 905, 786, 548, 73, 146, 292, 584, 145, 290, 580, 137, 274, 549, 75, 150, 300, 600, 177, 354, 708, 393, 787, 550, 77, 154, 308, 616, 209, 418, 836, 649, 275, 551, 79, 158, 316, 632, 241, 482, 965, 906, 788, 553, 83, 166, 332, 664, 305, 610, 197, 394, 789, 554, 85, 170, 340, 680, 337, 674, 325, 650, 277, 555, 87, 174, 348, 696, 369, 738, 453, 907, 790, 556, 89, 178, 356, 712, 401, 802, 581, 139, 278, 557, 91, 182, 364, 728, 433, 866, 709, 395, 791, 558, 93, 186, 372, 744, 465, 930, 837, 651, 279, 559, 95, 190, 380, 760, 497, 995, 966, 908, 792, 561, 99, 198, 396, 793, 562, 101, 202, 404, 808, 593, 163, 326, 652, 281, 563, 103, 206, 412, 824, 625, 227, 454, 909, 794, 564, 105, 210, 420, 840, 657, 291, 582, 141, 282, 565, 107, 214, 428, 856, 689, 355, 710, 397, 795, 566, 109, 218, 436, 872, 721, 419, 838, 653, 283, 567, 111, 222, 444, 888, 753, 483, 967, 910, 796, 569, 115, 230, 460, 920, 817, 611, 199, 398, 797, 570, 117, 234, 468, 936, 849, 675, 327, 654, 285, 571, 119, 238, 476, 952, 881, 739, 455, 911, 798, 572, 121, 242, 484, 968, 913, 803, 583, 143, 286, 573, 123, 246, 492, 984, 945, 867, 711, 399, 799, 574, 125, 250, 500, 1000, 977, 931, 839, 655, 287, 575, 127, 254, 508, 1017, 1010, 996, 969, 914, 804, 585, 147, 294, 588, 153, 306, 612, 201, 402, 805, 586, 149, 298, 596, 169, 338, 676, 329, 658, 293, 587, 151, 302, 604, 185, 370, 740, 457, 915, 806, 589, 155, 310, 620, 217, 434, 868, 713, 403, 807, 590, 157, 314, 628, 233, 466, 932, 841, 659, 295, 591, 159, 318, 636, 249, 498, 997, 970, 916, 809, 594, 165, 330, 660, 297, 595, 167, 334, 668, 313, 626, 229, 458, 917, 810, 597, 171, 342, 684, 345, 690, 357, 714, 405, 811, 598, 173, 346, 692, 361, 722, 421, 842, 661, 299, 599, 175, 350, 700, 377, 754, 485, 971, 918, 812, 601, 179, 358, 716, 409, 818, 613, 203, 406, 813, 602, 181, 362, 724, 425, 850, 677, 331, 662, 301, 603, 183, 366, 732, 441, 882, 741, 459, 919, 814, 605, 187, 374, 748, 473, 946, 869, 715, 407, 815, 606, 189, 378, 756, 489, 978, 933, 843, 663, 303, 607, 191, 382, 764, 505, 1011, 998, 972, 921, 819, 614, 205, 410, 820, 617, 211, 422, 844, 665, 307, 615, 207, 414, 828, 633, 243, 486, 973, 922, 821, 618, 213, 426, 852, 681, 339, 678, 333, 666, 309, 619, 215, 430, 860, 697, 371, 742, 461, 923, 822, 621, 219, 438, 876, 729, 435, 870, 717, 411, 823, 622, 221, 442, 884, 745, 467, 934, 845, 667, 311, 623, 223, 446, 892, 761, 499, 999, 974, 924, 825, 627, 231, 462, 925, 826, 629, 235, 470, 940, 857, 691, 359, 718, 413, 827, 630, 237, 474, 948, 873, 723, 423, 846, 669, 315, 631, 239, 478, 956, 889, 755, 487, 975, 926, 829, 634, 245, 490, 980, 937, 851, 679, 335, 670, 317, 635, 247, 494, 988, 953, 883, 743, 463, 927, 830, 637, 251, 502, 1004, 985, 947, 871, 719, 415, 831, 638, 253, 506, 1012, 1001, 979, 935, 847, 671, 319, 639, 255, 510, 1021, 1018, 1013, 1002, 981, 938, 853, 682, 341, 683, 343, 686, 349, 698, 373, 746, 469, 939, 854, 685, 347, 694, 365, 730, 437, 874, 725, 427, 855, 687, 351, 702, 381, 762, 501, 1003, 982, 941, 858, 693, 363, 726, 429, 859, 695, 367, 734, 445, 890, 757, 491, 983, 942, 861, 699, 375, 750, 477, 954, 885, 747, 471, 943, 862, 701, 379, 758, 493, 986, 949, 875, 727, 431, 863, 703, 383, 766, 509, 1019, 1014, 1005, 987, 950, 877, 731, 439, 878, 733, 443, 886, 749, 475, 951, 879, 735, 447, 894, 765, 507, 1015, 1006, 989, 955, 887, 751, 479, 958, 893, 763, 503, 1007, 990, 957, 891, 759, 495, 991, 959, 895, 767, 511, 1023, 1022, 1020, 1016, 1008, 992, 960, 896, 768, 512};
vector<int> loc = {0, 1, 2, 11, 3, 21, 12, 31, 4, 41, 22, 51, 13, 61, 32, 71, 5, 81, 42, 91, 23, 101, 52, 111, 14, 121, 62, 131, 33, 141, 72, 151, 6, 161, 82, 166, 43, 176, 92, 186, 24, 196, 102, 206, 53, 216, 112, 226, 15, 236, 122, 246, 63, 256, 132, 266, 34, 276, 142, 286, 73, 296, 152, 306, 7, 87, 162, 242, 83, 316, 167, 326, 44, 336, 177, 346, 93, 356, 187, 366, 25, 320, 197, 376, 103, 386, 207, 396, 54, 406, 217, 416, 113, 426, 227, 436, 16, 171, 237, 446, 123, 451, 247, 461, 64, 471, 257, 481, 133, 491, 267, 501, 35, 330, 277, 511, 143, 521, 287, 531, 74, 541, 297, 551, 153, 561, 307, 571, 8, 48, 88, 128, 163, 203, 243, 283, 84, 343, 317, 413, 168, 478, 327, 548, 45, 340, 337, 581, 178, 591, 347, 601, 94, 584, 357, 611, 188, 621, 367, 631, 26, 181, 321, 456, 198, 641, 377, 646, 104, 594, 387, 656, 208, 666, 397, 676, 55, 350, 407, 686, 218, 696, 417, 706, 114, 604, 427, 716, 228, 726, 437, 736, 17, 97, 172, 252, 238, 382, 447, 517, 124, 587, 452, 692, 248, 746, 462, 756, 65, 360, 472, 750, 258, 766, 482, 776, 134, 614, 492, 786, 268, 796, 502, 806, 36, 191, 331, 466, 278, 651, 512, 816, 144, 624, 522, 821, 288, 831, 532, 841, 75, 370, 542, 760, 298, 851, 552, 861, 154, 634, 562, 871, 308, 881, 572, 891, 9, 29, 49, 69, 89, 109, 129, 149, 164, 184, 204, 224, 244, 264, 284, 304, 85, 324, 344, 364, 318, 394, 414, 434, 169, 459, 479, 499, 328, 529, 549, 569, 46, 201, 341, 476, 338, 599, 582, 629, 179, 644, 592, 674, 348, 704, 602, 734, 95, 380, 585, 754, 358, 774, 612, 804, 189, 649, 622, 839, 368, 859, 632, 889, 27, 107, 182, 262, 322, 392, 457, 527, 199, 597, 642, 702, 378, 772, 647, 857, 105, 390, 595, 770, 388, 901, 657, 903, 209, 659, 667, 913, 398, 905, 677, 923, 56, 211, 351, 486, 408, 661, 687, 826, 219, 669, 697, 933, 418, 915, 707, 938, 115, 400, 605, 780, 428, 907, 717, 948, 229, 679, 727, 958, 438, 925, 737, 968, 18, 58, 98, 138, 173, 213, 253, 293, 239, 353, 383, 423, 448, 488, 518, 558, 125, 410, 588, 618, 453, 663, 693, 723, 249, 689, 747, 793, 463, 828, 757, 878, 66, 221, 361, 496, 473, 671, 751, 836, 259, 699, 767, 920, 483, 935, 777, 965, 135, 420, 615, 790, 493, 917, 787, 978, 269, 709, 797, 981, 503, 940, 807, 988, 37, 117, 192, 272, 332, 402, 467, 537, 279, 607, 652, 712, 513, 782, 817, 867, 145, 430, 625, 800, 523, 909, 822, 954, 289, 719, 832, 984, 533, 950, 842, 998, 76, 231, 371, 506, 543, 681, 761, 846, 299, 729, 852, 943, 553, 960, 862, 1008, 155, 440, 635, 810, 563, 927, 872, 1002, 309, 739, 882, 991, 573, 970, 892, 1013, 1023, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 165, 175, 185, 195, 205, 215, 225, 235, 245, 255, 265, 275, 285, 295, 305, 86, 241, 315, 325, 335, 345, 355, 365, 319, 375, 385, 395, 405, 415, 425, 435, 170, 445, 450, 460, 470, 480, 490, 500, 329, 510, 520, 530, 540, 550, 560, 570, 47, 127, 202, 282, 342, 412, 477, 547, 339, 580, 590, 600, 583, 610, 620, 630, 180, 455, 640, 645, 593, 655, 665, 675, 349, 685, 695, 705, 603, 715, 725, 735, 96, 251, 381, 516, 586, 691, 745, 755, 359, 749, 765, 775, 613, 785, 795, 805, 190, 465, 650, 815, 623, 820, 830, 840, 369, 759, 850, 860, 633, 870, 880, 890, 28, 68, 108, 148, 183, 223, 263, 303, 323, 363, 393, 433, 458, 498, 528, 568, 200, 475, 598, 628, 643, 673, 703, 733, 379, 753, 773, 803, 648, 838, 858, 888, 106, 261, 391, 526, 596, 701, 771, 856, 389, 769, 900, 902, 658, 912, 904, 922, 210, 485, 660, 825, 668, 932, 914, 937, 399, 779, 906, 947, 678, 957, 924, 967, 57, 137, 212, 292, 352, 422, 487, 557, 409, 617, 662, 722, 688, 792, 827, 877, 220, 495, 670, 835, 698, 919, 934, 964, 419, 789, 916, 977, 708, 980, 939, 987, 116, 271, 401, 536, 606, 711, 781, 866, 429, 799, 908, 953, 718, 983, 949, 997, 230, 505, 680, 845, 728, 942, 959, 1007, 439, 809, 926, 1001, 738, 990, 969, 1012, 1022, 19, 39, 59, 79, 99, 119, 139, 159, 174, 194, 214, 234, 254, 274, 294, 240, 314, 334, 354, 374, 384, 404, 424, 444, 449, 469, 489, 509, 519, 539, 559, 126, 281, 411, 546, 579, 589, 609, 619, 454, 639, 654, 664, 684, 694, 714, 724, 250, 515, 690, 744, 748, 764, 784, 794, 464, 814, 819, 829, 758, 849, 869, 879, 67, 147, 222, 302, 362, 432, 497, 567, 474, 627, 672, 732, 752, 802, 837, 887, 260, 525, 700, 855, 768, 899, 911, 921, 484, 824, 931, 936, 778, 946, 956, 966, 136, 291, 421, 556, 616, 721, 791, 876, 494, 834, 918, 963, 788, 976, 979, 986, 270, 535, 710, 865, 798, 952, 982, 996, 504, 844, 941, 1006, 808, 1000, 989, 1011, 1021, 38, 78, 118, 158, 193, 233, 273, 313, 333, 373, 403, 443, 468, 508, 538, 280, 545, 578, 608, 638, 653, 683, 713, 514, 743, 763, 783, 813, 818, 848, 868, 146, 301, 431, 566, 626, 731, 801, 886, 524, 854, 898, 910, 823, 930, 945, 955, 290, 555, 720, 875, 833, 962, 975, 985, 534, 864, 951, 995, 843, 1005, 999, 1010, 1020, 77, 157, 232, 312, 372, 442, 507, 544, 577, 637, 682, 742, 762, 812, 847, 300, 565, 730, 885, 853, 897, 929, 944, 554, 874, 961, 974, 863, 994, 1004, 1009, 1019, 156, 311, 441, 576, 636, 741, 811, 564, 884, 896, 928, 873, 973, 993, 1003, 1018, 310, 575, 740, 883, 895, 972, 992, 1017, 574, 894, 971, 1016, 893, 1015, 1014};

vector<int> paint(int n)
{
	int k = 10;
	vector<int> labels(n, 0);
	for (int i = 0; i+k-1 < n; i++) labels[i+k-1] = path[i]&1;
	labels.push_back(k);

	return labels;
}

int find_location(int n, vector<int> c)
{
	for (int i = 0; i < c.size(); i++) if (c[i] == -1) return n-i;
	int resp = 0;
	for (auto x : c) resp = (resp<<1) + x;
	return loc[resp];
}

Compilation message (stderr)

squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:20:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for (int i = 0; i < c.size(); i++) if (c[i] == -1) return n-i;
      |                  ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55