QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#181964#4892. 序列hos_lyric#50 154ms73556kbC++142.7kb2023-09-17 06:50:432024-07-04 02:01:14

Judging History

This is the latest submission verdict.

  • [2024-07-04 02:01:14]
  • Judged
  • Verdict: 50
  • Time: 154ms
  • Memory: 73556kb
  • [2023-09-17 06:50:43]
  • Submitted

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


int med(int a, int b, int c) {
  return (a < b)
      ? ((a < c) ? ((b < c) ? b : c) : a)
      : ((b < c) ? ((a < c) ? a : c) : b);
}

int N, M;
int U[100'010][3];
vector<int> X;


namespace brute {
vector<int> run() {
  vector<int> perm(N);
  for (int u = 0; u < N; ++u) perm[u] = u;
  do {
    vector<int> xs(N, 0);
    for (int i = 0; i < M; ++i) {
      const int p = med(perm[U[i][0]], perm[U[i][1]], perm[U[i][2]]);
      if (!xs[p]) {
        xs[p] = X[i];
      }
      if (xs[p] != X[i]) {
        goto failed;
      }
    }
    {
      int x = 1;
      for (int p = 0; p < N; ++p) {
        if (!xs[p]) {
          xs[p] = x;
        }
        if (x > xs[p]) {
          goto failed;
        }
        x = xs[p];
      }
      vector<int> ans(N, -1);
      for (int u = 0; u < N; ++u) {
        ans[u] = xs[perm[u]];
      }
      return ans;
    }
   failed:{}
  } while (next_permutation(perm.begin(), perm.end()));
  return {};
}
}  // brute


int main() {
  for (; ~scanf("%d%d", &N, &M); ) {
    X.resize(M);
    for (int i = 0; i < M; ++i) {
      scanf("%d%d%d%d", &U[i][0], &U[i][1], &U[i][2], &X[i]);
      --U[i][0];
      --U[i][1];
      --U[i][2];
    }
    
    const auto ans = brute::run();
    if (!ans.empty()) {
      puts("YES");
      for (int u = 0; u < N; ++u) {
        if (u) printf(" ");
        printf("%d", ans[u]);
      }
      puts("");
    } else {
      puts("NO");
    }
  }
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 41ms
memory: 3804kb

input:

10 10
6 3 10 133562624
8 7 6 685486592
4 2 7 332482851
10 8 9 211550017
2 10 1 165556251
10 8 5 211550017
6 8 2 332482851
4 9 2 332482851
8 1 4 193658790
9 6 10 728674154

output:

YES
165556251 332482851 1 193658790 332482851 728674154 685486592 211550017 728674154 133562624

result:

ok solution is correct

Test #2:

score: 0
Accepted
time: 112ms
memory: 3808kb

input:

10 9
5 3 7 489042696
10 9 3 489042696
5 9 4 589265757
1 3 7 489042696
9 3 10 489042696
2 8 7 402617168
2 4 5 564742148
1 8 3 615037121
2 8 4 564742148

output:

YES
615037121 1 489042696 564742148 589265757 615037121 402617168 615037121 615037121 489042696

result:

ok solution is correct

Test #3:

score: 0
Accepted
time: 8ms
memory: 3816kb

input:

9 9
3 8 4 385329352
1 4 5 826490084
4 5 9 866319564
2 4 1 449825973
8 3 5 385329352
6 2 9 88759441
3 6 9 88759441
6 8 9 385329352
4 8 1 449825973

output:

YES
449825973 1 1 826490084 866319564 88759441 866319564 385329352 866319564

result:

ok solution is correct

Test #4:

score: 0
Accepted
time: 154ms
memory: 3976kb

input:

10 10
1 9 6 957652738
9 7 1 934947905
9 10 8 507132050
5 2 8 162855738
2 2 8 537894544
9 9 9 266667281
3 3 8 158325440
2 7 9 752321309
10 3 1 104743493
4 10 10 799817379

output:

NO

result:

ok no solution

Test #5:

score: 0
Accepted
time: 3ms
memory: 3624kb

input:

8 9
7 4 7 187362209
5 1 1 634248682
2 3 2 664513540
3 2 4 161388361
5 1 3 463648080
8 1 6 485087787
6 3 6 689280466
3 6 8 116609606
7 2 7 399054929

output:

NO

result:

ok no solution

Test #6:

score: 0
Accepted
time: 49ms
memory: 4064kb

input:

10 8
5 6 10 861588864
10 1 8 608002433
8 3 4 196795234
1 8 3 285047219
9 7 5 480962478
6 10 1 780552157
3 4 2 190713929
7 5 6 780552157

output:

YES
285047219 1 190713929 196795234 861588864 780552157 285047219 608002433 480962478 861588864

result:

ok solution is correct

Test #7:

score: 0
Accepted
time: 9ms
memory: 3808kb

input:

10 5
6 5 1 644007358
4 2 1 644007358
8 5 1 672067709
7 2 1 845787134
9 8 5 672067709

output:

YES
1 845787134 845787134 644007358 672067709 644007358 845787134 672067709 845787134 845787134

result:

ok solution is correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

9 6
9 6 3 408886589
3 2 1 680261634
8 4 1 540611446
6 3 2 680261634
5 2 1 540611446
7 3 2 680261634

output:

YES
1 680261634 680261634 540611446 540611446 1 680261634 680261634 408886589

result:

ok solution is correct

Subtask #2:

score: 0
Time Limit Exceeded

Test #9:

score: 0
Time Limit Exceeded

input:

40 9880
4 19 31 610502845
10 19 33 190412843
21 24 39 649028784
16 22 40 569593239
5 9 37 550862419
11 23 40 654613112
6 18 23 492267246
22 23 30 538715841
6 16 24 407919735
5 16 18 388907784
2 16 18 388907784
21 24 28 281403057
7 12 27 451830401
3 11 16 508407438
15 33 36 561955959
6 23 29 70605893...

output:

YES
877488996 197498120 508407438 610502845 209356929 706058934 655952999 624132238 550862419 32695410 654613112 72694954 399757770 396827347 561955959 407919735 779328631 388907784 190412843 657895429 832003778 569593239 492267246 32695410 718125822 812463588 451830401 281403057 877488996 538715841...

result:


Subtask #3:

score: 30
Accepted

Dependency #1:

100%
Accepted

Test #16:

score: 30
Accepted
time: 48ms
memory: 44572kb

input:

1000 996
527 924 774 540173899
415 382 71 188751360
884 463 698 125924043
810 890 663 324838547
366 94 515 666179824
192 778 279 847431254
769 80 245 922736826
529 115 418 778769842
446 715 604 875242794
160 625 423 424822525
877 194 974 556338768
198 70 696 237534851
8 304 726 470021479
496 953 866...

output:

YES
2972186 2972186 670603801 824109436 194070621 614405181 356247025 420489663 2972186 950845418 609512045 609512045 857879636 824109436 626441474 607162501 664929448 2972186 409659940 703780779 640834798 585395354 766586241 441780827 209233215 734690663 439151771 2972186 846644135 169726917 324838...

result:

ok solution is correct

Test #17:

score: 0
Accepted
time: 63ms
memory: 73556kb

input:

996 1000
848 457 378 880385818
743 926 806 553228470
619 544 861 974849688
698 389 756 951371810
120 71 828 505821547
318 940 217 549943590
536 852 664 540115645
107 749 796 966841837
905 659 358 596025315
622 988 532 365141303
742 687 206 69113219
830 712 5 484296740
107 473 839 302448568
453 307 7...

output:

NO

result:

ok no solution

Test #18:

score: 0
Accepted
time: 33ms
memory: 42516kb

input:

990 988
723 217 736 529714749
380 396 260 409316596
716 401 619 788977572
232 40 909 164972335
323 646 767 742422834
71 268 229 498183446
695 825 949 605491713
447 539 73 644621097
420 81 160 368595699
425 287 797 536503051
385 36 451 515447677
952 980 356 506411673
149 355 67 955377149
726 594 192 ...

output:

YES
443272028 32792787 353952887 423457295 32792787 554132482 32792787 905142170 166672290 404755886 32792787 732938991 32792787 32792787 458153570 32792787 577930774 801254851 851220356 393414923 32792787 886695682 643346815 32792787 794870892 705435825 942112175 480960502 739916080 681118387 32792...

result:

ok solution is correct

Test #19:

score: 0
Accepted
time: 39ms
memory: 29672kb

input:

1000 992
358 307 292 715383877
889 622 482 680348743
106 61 16 780021827
967 840 355 799032574
7 6 2 371465877
886 277 143 488646126
196 7 6 325091271
292 274 172 378495286
356 297 226 247061041
298 136 30 288877994
399 191 33 108831408
595 350 48 342498526
406 5 3 666420994
321 146 69 878509167
699...

output:

YES
568892025 371465877 240147313 382659615 912032235 535835515 325091271 506493571 388344702 822893994 719429987 303866276 583326332 589898523 777989666 535270750 36369171 277896857 542030738 560500043 616674702 498011517 889586844 436151328 118249813 335897947 365646875 783512918 494764081 2139625...

result:

ok solution is correct

Test #20:

score: 0
Accepted
time: 42ms
memory: 40772kb

input:

1000 995
93 88 83 205161273
59 54 47 272815050
976 968 967 128081945
491 486 476 163208281
964 960 953 393463398
126 122 119 919973605
251 243 241 268012077
401 398 390 888396262
786 777 773 821327852
264 256 250 387688185
107 104 95 764563667
198 195 185 421528348
18 14 4 465222052
163 154 149 4425...

output:

YES
465222052 27884338 420272005 465222052 420272005 725814201 465222052 554351793 757386571 554351793 290177907 465222052 164869035 465222052 578945293 725814201 574834092 774812229 508474159 527586554 465222052 475145071 574834092 854236804 757386571 508474159 164869035 305048016 508663785 2252654...

result:

ok solution is correct

Test #21:

score: 0
Accepted
time: 43ms
memory: 44712kb

input:

1000 1000
556 922 96 247240976
370 478 526 363454712
150 642 778 518784471
643 799 624 143452980
802 129 973 753138409
199 215 390 501598040
583 526 122 48846823
854 611 985 605244939
49 338 443 128617908
273 232 409 244385789
653 658 559 488952689
407 210 464 433805586
585 90 940 614614430
200 884 ...

output:

NO

result:

ok no solution

Test #22:

score: 0
Accepted
time: 39ms
memory: 42440kb

input:

1000 998
629 816 724 126263144
621 897 391 796546541
696 322 185 803804896
305 790 889 153079778
330 652 692 609221623
253 703 517 578803480
537 563 346 245597626
231 706 863 483185655
480 852 407 473711558
156 1 967 762984005
842 945 498 943018627
513 799 78 86152666
703 517 550 578803480
168 506 9...

output:

YES
535370966 653909866 527164019 875149419 704759861 576529855 159013463 545426727 693134038 15823871 15823871 15823871 537710478 906800639 15823871 15823871 756105032 461649456 603236285 603236285 15823871 459871381 864400294 505777059 305616160 727284214 642678444 642678444 15823871 15823871 4389...

result:

ok solution is correct

Test #23:

score: 0
Accepted
time: 29ms
memory: 30308kb

input:

1000 997
357 347 345 733358338
682 672 663 209734493
393 387 380 305734825
627 626 625 324357526
928 919 914 438604806
625 616 610 417853070
540 537 531 807315869
886 885 878 777205250
752 750 748 348526994
679 678 675 276712558
970 969 961 376456558
518 516 506 571223812
264 256 255 562733931
23 20...

output:

YES
997630534 997630534 21980339 666922803 787030151 251259941 787030151 410528085 284506465 666922803 785449789 785449789 375712613 251259941 251259941 251259941 301736605 410528085 666922803 187474183 138591831 284506465 449165229 483096393 301736605 885066723 369361134 138591831 483096393 1874741...

result:

ok solution is correct

Test #24:

score: 0
Accepted
time: 43ms
memory: 41344kb

input:

1000 998
188 595 689 592674202
126 841 768 505688775
274 1000 351 565885054
767 460 705 439050630
61 626 381 387458774
607 444 978 618476232
264 583 900 850042952
53 722 698 40237254
482 112 552 162817181
242 545 956 648781127
964 186 989 830125903
475 685 786 521769463
841 768 13 478559108
409 443 ...

output:

NO

result:

ok no solution

Test #25:

score: 0
Accepted
time: 38ms
memory: 29408kb

input:

1000 997
224 221 215 685183418
765 756 753 345268843
880 874 871 547734181
796 787 778 764396807
480 470 469 896165180
700 698 690 500019202
450 442 438 667969122
151 146 141 549351752
819 810 804 186861970
537 531 527 310783900
884 881 873 888208832
590 588 583 659624517
152 150 144 323089371
618 6...

output:

NO

result:

ok no solution

Subtask #4:

score: 0
Skipped

Dependency #2:

0%