Submission #308289

#	Time	Username	Problem	Language	Result	Execution time	Memory
308289		joylintp	Painting Squares (IOI20_squares)	C++14	100 / 100	153 ms	656 KiB

squares

#include "squares.h"
#include<bits/stdc++.h>
using namespace std;

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

vector<int> paint(int n)
{
    vector<int> ret;
	for (int i = 0; i < n; i++)
        ret.push_back(perm[i] - '0');
    ret.push_back(min(10, n));

	return ret;
}

int find_location(int n, vector<int> c)
{
    int cnt = 0;
    for (int i = c.size() - 1; i >= 0; i--)
        if (c[i] == -1)
            cnt++;
        else
            break;

    if (n < 10)
        return cnt;
    else if (cnt)
        return n - 10 + cnt;
    else
    {
        int ret = 0;
        for (int i = 0; i < 10; i++)
            ret = ret * 2 + c[i];
        return pos[ret];
    }
}

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