QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#134140#4892. 序列raymond_720 78ms1768kbC++141.6kb2023-08-03 08:54:552023-08-03 08:54:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-03 08:54:56]
  • 评测
  • 测评结果:20
  • 用时:78ms
  • 内存:1768kb
  • [2023-08-03 08:54:55]
  • 提交

answer

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

const int N = 1e5 + 20;
const int Ding = 88281;

int n, m, a[N];
struct Infor
{
	int i, j, k, x;
	void init(){scanf("%d%d%d%d", &i, &j, &k, &x);}
}I[N];

int max3(int a, int b, int c) {return max(max(a, b), c);}
int min3(int a, int b, int c) {return min(min(a, b), c);}

namespace sub1
{
	const int N1 = 12;
	int p[N1], rk[N1], seq[N1];
	void solve()
	{
		for(int i = 1; i <= n; i ++) p[i] = i;
		do
		{
			for(int i = 1; i <= n; i ++) seq[i] = 0;
			bool ex = 1;
			for(int tp = 1, i, j, k; tp <= m; tp ++)
			{
				i = I[tp].i; j = I[tp].j; k = I[tp].k;
				if(p[i] > p[j]) swap(i, j);
				if(p[i] > p[k]) swap(i, k);
				if(p[j] > p[k]) swap(j, k);
				// printf("(%d, %d, %d)\n", i, j, k);
				if(seq[j] && seq[j] != I[tp].x) {ex = 0; break;}
				seq[j] = I[tp].x;
			}
			for(int i = 1; i <= n; i ++)
				if(!seq[i]) seq[i] = (seq[p[i - 1]] ? seq[p[i - 1]] : 1);
			for(int tp = 1, i, j, k; tp <= m; tp ++)
			{
				i = I[tp].i; j = I[tp].j; k = I[tp].k;
				if(seq[i] + seq[j] + seq[k] - max3(seq[i], seq[j], seq[k]) - min3(seq[i], seq[j], seq[k]) != I[tp].x)
					{ex = 0; break;}
			}
			if(ex)
			{
				puts("YES");
				for(int i = 1; i <= n; i ++) printf("%d ", seq[i]);
				return ;
			}
		}while(next_permutation(p + 1, p + n + 1));
		puts("NO");
	}
}

int main()
{
	// freopen("C.in", "r", stdin);
	// freopen("C.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; i ++) I[i].init();
	if(n <= 10 && m <= 10) {sub1::solve(); return 0;}
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 19ms
memory: 1764kb

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 133562624 193658790 211550017 728674154 685486592 211550017 728674154 1 

result:

ok solution is correct

Test #2:

score: 0
Accepted
time: 26ms
memory: 1768kb

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 402617168 489042696 564742148 589265757 1 1 615037121 615037121 489042696 

result:

ok solution is correct

Test #3:

score: 0
Accepted
time: 4ms
memory: 1620kb

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
826490084 88759441 88759441 449825973 866319564 88759441 385329352 385329352 866319564 

result:

ok solution is correct

Test #4:

score: 0
Accepted
time: 78ms
memory: 1512kb

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: 1ms
memory: 1504kb

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: 12ms
memory: 1760kb

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 190713929 1 196795234 861588864 780552157 480962478 608002433 1 861588864 

result:

ok solution is correct

Test #7:

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

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 1 644007358 845787134 644007358 845787134 672067709 672067709 845787134 

result:

ok solution is correct

Test #8:

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

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 408886589 540611446 540611446 1 

result:

ok solution is correct

Subtask #2:

score: 0
Wrong Answer

Test #9:

score: 0
Wrong Answer
time: 2ms
memory: 1760kb

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:

wrong output format Unexpected end of file - token expected

Subtask #3:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #16:

score: 0
Wrong Answer
time: 0ms
memory: 1764kb

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:

wrong output format Unexpected end of file - token expected

Subtask #4:

score: 0
Skipped

Dependency #2:

0%