11926 - Multitasking

All about problems in Volume 119. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 11926 - Multitasking

Post by uDebug »

@li_kuet , brianfry713, vector9x,
Thanks for the great test cases!
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.
Top
Robert_Alonso
New poster
Posts: 8
Joined: Fri Jul 25, 2014 2:04 am

Re: 11926 - Multitasking

Post by Robert_Alonso »

Hi, I've checked and passed all the previous test cases posted here, but I'm still getting WA :( Thanks for your help.

Code: Select all

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#define N 1000000
using namespace std;

int sched[1000010];

int main(void){
	int n, m, s, e, p;
	while(cin >> n >> m, n|m){
		memset(sched, 0, sizeof sched);
		bool conflict = false, processed = false;
		for(int i=0; i<n; i++){
			cin >> s >> e;
			if(conflict) continue;
			if(s+1<=N && sched[s+1] && e-s>1){conflict = true; continue;}
			if(e-1>=0 && sched[e-1] && e-s>1){conflict = true; continue;}
			if(e-s==1 && sched[s] && sched[e]){conflict = true; continue;}
			if(e-s==0 && sched[s]){conflict = true; continue;}
			for(int j=s; j<=e; j++)
				if(j!=s && j!=e && sched[j])
					{conflict = true; break;}
				else sched[j] = 1;
		}				
		if(conflict) {printf("CONFLICT\n"); processed = true;}
		for(int i=0; i<m; i++){
			cin >> s >> e >> p;
			if(conflict) continue;
			while(s <= 1000000){
				if(s+1<=N && sched[s+1]){conflict = true; break;}
				if(e-1>=0 && sched[e-1]){conflict = true; break;}
				if(e-s==1 && sched[s] && sched[e]){conflict = true; break;}
				if(e-s==0 && sched[s]){conflict = true; break;}
				for(int j=s; j<=e; j++)
					if(j!=s && j!=e && sched[j])
						{conflict = true; break;}
					else sched[j] = 1;
				if(conflict) break;
				s += p; e += p;
				if(e>1000000) e=1000000;
			}					
		}		
		if(conflict && !processed) printf("CONFLICT\n");
		else if(!processed) printf("NO CONFLICT\n");
	}
	return 0;
}
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11926 - Multitasking

Post by brianfry713 »

Input:

Code: Select all

1 2
79605 256359
923378 995289 927224
964536 994182 357264
4 0
528005 562991
202299 862624
65954 431983
820798 869954
4 0
422364 761696
952672 954943
994775 998813
637936 776903
4 3
774481 834708
297270 601398
139492 288558
180892 996530
98789 116978 650329
626794 951884 370642
458628 781292 573184
2 0
587791 884830
63208 439380
1 1
668363 691124
359157 540314 687586
1 1
281785 639064
828058 986855 187203
2 3
285254 360489
758483 978839
989819 991983 890487
768786 939504 687936
928130 955296 610345
4 1
519777 680468
631096 980779
108713 416252
897669 977731
80016 878096 701047
4 2
887459 905001
710144 930003
230827 605905
603261 702038
115476 372402 509626
335330 675107 955781
3 3
982895 999124
344917 403033
255302 294245
841165 998276 972055
578884 848772 152585
279877 389495 788989
2 0
17386 775089
933557 986346
3 4
119987 366140
699131 917366
726279 750120
598291 864260 156037
222497 337395 888601
477800 560740 729975
201417 584745 827108
3 3
624458 806829
437047 852865
493485 620604
687340 846469 459998
186147 456505 97490
214389 269646 554066
4 2
669539 948597
681642 790523
980918 990614
369836 583217
816375 915941 485967
160955 455803 134935
1 4
570785 742112
453043 749111 820642
398583 759264 525240
53823 496490 741163
408194 946978 717604
1 3
764330 973676
251415 393656 741385
139750 471028 76092
229503 958221 237906
0 3
540811 647196 479077
155016 480358 23711
975062 989184 544695
3 4
162315 978066
671505 849162
992577 995585
693035 834097 778957
462950 507458 520341
602700 977872 596432
832203 893719 350689
3 1
891373 950705
396770 767834
362274 421329
539949 773640 483065
2 3
162368 503452
506577 579729
863607 898963 709376
620513 804773 172449
159663 311243 291766
2 3
123909 267015
911430 986479
915495 987254 944111
830765 901196 306385
768596 774223 877245
0 4
193391 850559 374357
699968 951920 238060
849802 870850 377036
777786 982532 537932
0 1
5353 319104 794949
3 0
667635 944985
537088 731685
267681 755971
1 3
849415 923889
804925 948399 24165
254440 518086 242360
199979 653134 609699
1 1
387240 467092
913229 943522 903536
4 1
697707 715988
169375 273086
876921 904624
494259 838971
129740 237981 182783
4 4
504301 784385
817217 829335
613024 960434
477219 944738
186324 469739 472921
573564 606155 387425
222794 943093 824312
176382 378279 781079
2 2
657928 696194
133763 366432
737459 903798 502262
235112 977576 8329
4 1
801945 976027
769114 859335
311657 977040
164955 272411
47500 271385 689504
3 0
28778 520234
578048 697771
347932 818451
2 1
351315 513589
693110 699547
290645 925945 343885
2 3
54582 204722
748279 771133
414956 871140 299650
579911 617949 865041
899837 983804 170976
3 4
654601 848683
444123 952780
554819 683483
476682 711198 219411
688291 883253 510498
135012 175547 326265
185250 244986 944174
1 0
875818 973411
2 0
429749 433071
355564 606701
2 3
632647 633447
452051 840715
160382 538240 25999
155564 597572 245409
362354 649313 755906
3 3
597966 669653
317098 847184
653144 846305
934645 974793 883446
390372 993648 696920
264436 821984 165017
3 2
320780 529320
895078 901677
393638 783989
636726 955220 684055
517580 735996 439960
4 1
554720 996941
566416 921354
906204 990251
548191 612692
900429 950176 260677
1 2
925826 997425
137716 727301 601093
5984 877825 599792
3 2
754202 782066
762248 844952
430348 591022
805227 867645 274755
539787 600933 888633
3 0
435458 534999
682584 736683
368460 535842
1 0
76724 737846
0 1
794717 918511 795488
4 0
66216 145094
73764 76001
886449 980865
143224 667777
1 3
330694 331226
165999 425436 427718
275796 644150 838796
644256 909422 489619
4 2
276977 322507
383384 892073
728585 752079
784533 962212
761616 899590 115658
618113 835428 426250
1 0
10115 476340
3 0
165844 190168
945577 979615
969168 972081
1 0
789550 980875
0 1
593891 824296 658597
1 2
959752 990357
629032 730298 515195
247144 629577 457796
1 2
985684 992049
155542 768411 693799
847778 916930 136445
0 2
738703 798369 541915
318636 501572 127342
3 3
301724 417979
726300 951689
671575 765483
461860 758503 639884
826323 836468 168455
920979 953574 212151
4 3
904446 922638
583441 857385
815241 881844
814455 867860
876850 964876 439484
521854 957134 816080
823578 930542 60237
4 3
933353 998893
248202 926153
891736 924463
257779 333383
73548 753206 446084
724863 804093 924908
826803 861559 740548
1 2
490243 934924
952798 953907 80623
35413 452150 904883
4 2
506506 589699
290676 423894
701419 754018
982153 987356
639781 903515 220824
627836 824250 946921
0 2
290915 659129 460885
453088 513249 468291
3 2
914222 975440
815008 931462
29936 641237
532350 725542 696525
823026 953852 915780
3 1
543872 747929
477876 576652
509643 596972
228735 742802 994649
2 0
970498 982445
900866 955461
3 2
871359 881448
532467 639786
695766 965620
615733 649525 471774
957258 970273 903906
1 0
965794 993954
2 0
72233 857263
477650 814763
1 3
213280 240331
7037 800354 769779
545883 714404 641486
693213 963864 724047
1 3
339131 646553
645326 721068 592506
548748 718758 653326
514542 945007 709381
1 0
38694 298886
1 2
275406 490440
209736 759819 635138
978394 991700 985093
1 2
866811 956588
947516 998910 719397
642699 764144 534241
3 3
28499 79304
269498 632260
113038 959289
217259 772716 311359
486968 875848 586842
969958 989518 870070
2 4
697235 917342
911987 967307
492139 657694 721803
534522 735188 364796
222230 916968 600294
977187 984086 521822
1 0
634236 960623
0 2
109198 984734 891501
695665 725966 170334
3 3
944677 952423
152920 356383
554578 805179
184455 380888 698178
230185 514275 921022
808743 869797 898380
1 2
144181 631017
950213 951280 95445
773180 923981 530121
2 1
934739 963952
385753 576021
297370 782211 653764
0 1
815808 825180 553607
4 3
711850 996727
414414 654367
850194 976992
785607 997597
13826 137251 975710
108518 429446 581135
156754 173758 884166
3 3
269141 860234
823658 967395
761571 989041
748336 896807 391479
819336 907501 997843
531185 784574 929943
1 1
795973 902304
444029 480342 559763
2 2
68239 953659
593572 956002
918818 966858 288131
706459 968502 629311
4 2
643467 869435
688832 785581
783328 865962
66489 127971
898058 915814 871061
347712 749992 694549
1 4
253486 713749
74839 440258 800419
186910 453062 720163
908973 961297 427484
740357 813980 641905
2 3
605315 744279
748561 880194
357737 869472 740796
774294 909556 611857
122005 479597 306405
3 1
558711 577865
869885 877431
997596 999662
517992 721391 485629
0 1
743122 807235 821376
3 4
426104 557778
421600 985572
11808 650525
591898 859849 566550
202876 810378 205267
26600 27344 482148
103810 277185 352198
2 1
925699 930346
325954 762927
981406 989460 672617
2 0
266517 350353
270814 327997
1 1
413898 454905
714457 917719 874016
4 3
77240 948509
522456 574501
566242 791242
945165 991859
224662 735327 128244
550616 640193 109802
574537 991191 568024
0 1
697221 800099 695173
2 4
108913 274847
564075 889144
949466 982197 492924
545205 866627 533557
139965 841985 666839
85129 512515 891892
1 1
959761 993446
887922 943070 820516
2 0
111654 693554
680603 896176
1 0
434083 692618
0 0
AC output:

Code: Select all

CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
NO CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
NO CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
NO CONFLICT
CONFLICT
NO CONFLICT
Check input and AC output for thousands of problems on uDebug!
Top
Robert_Alonso
New poster
Posts: 8
Joined: Fri Jul 25, 2014 2:04 am

Re: 11926 - Multitasking

Post by Robert_Alonso »

brianfry713, in the 24th test case you provided:

Code: Select all

0 1
5353 319104 794949
I couldn't figure out why the AC output was "CONFLICT". If the period is 794949, I'd think that there's no conflict. Thank you very much for your answer :)
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11926 - Multitasking

Post by brianfry713 »

I edited my previous post and corrected the I/O.
Input:

Code: Select all

1 1
999999 1000000
999998 999999 2
0 0
AC output: NO CONFLICT
Check input and AC output for thousands of problems on uDebug!
Top
just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 11926 - Multitasking

Post by just_yousef »

what is wrong with my code ?? I passed all test cases in this post and still getting WA :( :(

Code: Select all

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

int n, m, a, b, c;
vector<pair<pair<int, int>, int> > arr;
char ans[][33] = { "CONFLICT", "NO CONFLICT" };
int test(int x, int y, int z, int g) {

	return ((x > z && x < g) || (y > z && y < g) || (z > x && z < y)
			|| (g > x && g < y) || (make_pair(x, y) == make_pair(z, g)));
}
int main(int argc, char **argv) {
#ifndef ONLINE_JUDGE
	freopen("a.in", "r", stdin);
#endif
	while (cin >> n >> m && (n + m)) {
		arr.clear();
		bool f = 1;
		for (int i = 0; i < n; ++i) {
			cin >> a >> b;
			if(a > b)swap(a,b);
			arr.push_back(make_pair(make_pair(a, b), 0));

		}
		for (int i = 0; i < m; ++i) {
			cin >> a >> b >> c;
			if(a > b)swap(a,b);
			arr.push_back(make_pair(make_pair(a, b), c));
			if (b - a > c && !c)
				f = 0;
		}
		for (size_t i = 0; i < arr.size(); ++i) {
			for (size_t j = 0; j < arr.size(); ++j) {
				if (i == j)
					continue;
				int x = arr[i].first.first, y = arr[i].first.second, cst =
						arr[i].second;
				while (x <= arr[j].first.second) {
					if (test(x, y, arr[j].first.first, arr[j].first.second)) {
						f = 0;
						break;
					}
					if (!cst)
						break;
					x += cst;
					y += cst;
				}
			}
		}
		cout << ans[f] << endl;
	}
	return 0;
}
Top
brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11926 - Multitasking

Post by brianfry713 »

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!
Top
Post Reply

Return to “Volume 119 (11900-11999)”