Submission #307781

#	Time	Username	Problem	Language	Result	Execution time	Memory
307781		b00n0rp	Painting Squares (IOI20_squares)	C++17	100 / 100	155 ms	716 KiB

squares

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

Compilation message (stderr)

squares.cpp: In function 'std::vector<int> paint(int)':
squares.cpp:27:8: warning: unused variable 'f2' [-Wunused-variable]
   27 |   bool f2 = (s.find(cur2) == s.end());
      |        ^~
squares.cpp: In function 'int find_location(int, std::vector<int>)':
squares.cpp:53:1: warning: control reaches end of non-void function [-Wreturn-type]
   53 | }
      | ^

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