QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#181963 | #4892. 序列 | hos_lyric# | 20 | 112ms | 4068kb | C++14 | 2.7kb | 2023-09-17 06:49:36 | 2024-07-04 02:01:14 |
Judging History
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+c-max({a,b,c})-min({a,b,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: 33ms
memory: 4032kb
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: 94ms
memory: 4064kb
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: 6ms
memory: 3996kb
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: 112ms
memory: 3648kb
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: 2ms
memory: 3604kb
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: 40ms
memory: 4068kb
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: 6ms
memory: 3872kb
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: 1ms
memory: 3800kb
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:
result:
Subtask #3:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #16:
score: 0
Time Limit Exceeded
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:
result:
Subtask #4:
score: 0
Skipped
Dependency #2:
0%