Task: | Lucky-SAT |
Sender: | Team Olari |
Submission time: | 2016-09-13 18:18:48 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.05 s | details |
#3 | ACCEPTED | 0.06 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.06 s | details |
#6 | ACCEPTED | 0.05 s | details |
#7 | ACCEPTED | 0.05 s | details |
#8 | ACCEPTED | 0.05 s | details |
#9 | ACCEPTED | 0.05 s | details |
#10 | ACCEPTED | 0.05 s | details |
#11 | ACCEPTED | 0.05 s | details |
#12 | ACCEPTED | 0.05 s | details |
#13 | ACCEPTED | 0.05 s | details |
#14 | ACCEPTED | 0.06 s | details |
#15 | ACCEPTED | 0.06 s | details |
#16 | ACCEPTED | 0.06 s | details |
#17 | ACCEPTED | 0.05 s | details |
#18 | ACCEPTED | 0.06 s | details |
#19 | ACCEPTED | 0.06 s | details |
#20 | ACCEPTED | 0.05 s | details |
#21 | ACCEPTED | 0.05 s | details |
#22 | ACCEPTED | 0.06 s | details |
#23 | ACCEPTED | 0.06 s | details |
#24 | ACCEPTED | 0.05 s | details |
#25 | ACCEPTED | 0.05 s | details |
#26 | ACCEPTED | 0.05 s | details |
#27 | ACCEPTED | 0.05 s | details |
#28 | ACCEPTED | 0.04 s | details |
#29 | ACCEPTED | 0.05 s | details |
#30 | ACCEPTED | 0.05 s | details |
#31 | ACCEPTED | 0.06 s | details |
Code
#include <iostream> #include <algorithm> using namespace std; int t[10001], dep[100], only_dep[100]; bool result[10001], sat[100]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n, m; cin >> n >> m; int r[n][7]; for (int i = 0; i < n; ++i) { for (int j = 0; j < 7; ++j) { cin >> r[i][j]; if (r[i][j] > 0) t[r[i][j]]++; else t[-r[i][j]]--; } } int satleft = n; for (int i = 1; i <= m; ++i) { result[i] = t[i] >= 0; for (int j = 0; j < n; ++j) { if (sat[j]) continue; bool remove = false; for (int k = 0; k < 7; ++k) { if (r[j][k] == (result[i] ? i : -i)) { remove = true; break; } } if (remove) { for (int k = 0; k < 7; ++k) { if (r[j][k] > 0) t[r[j][k]]--; else t[-r[j][k]]++; } sat[j] = 1; satleft--; } } } if (satleft != 0) { cout << "UNSAT\n"; } else { cout << "SAT\n"; for (int i = 1; i <= m; ++i) cout << result[i]; cout << endl; } }
Test details
Test 1
Verdict: ACCEPTED
input |
---|
8 10 4 -8 7 -10 -3 -1 2 -8 3 10 4 2 -5 9 6 4 2 -7 3 -5 8 7 9 -4 -5 3 10 6 ... |
correct output |
---|
SAT 1011110011 |
user output |
---|
SAT 0101011111 |
Test 2
Verdict: ACCEPTED
input |
---|
100 10000 -6030 -8236 5819 -6144 -5929 8... |
correct output |
---|
SAT 001110010010111100001111011100... |
user output |
---|
SAT 111111111111111111111111111101... |
Test 3
Verdict: ACCEPTED
input |
---|
9 7258 -4067 5723 6991 3302 -6175 -41... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111111111111111111111111111111... |
Test 4
Verdict: ACCEPTED
input |
---|
100 7 5 6 7 -2 1 4 3 -2 -7 1 -4 -5 -3 -6 1 2 -7 -6 3 4 5 5 -6 1 7 -3 2 4 ... |
correct output |
---|
SAT 0110101 |
user output |
---|
SAT 1000101 |
Test 5
Verdict: ACCEPTED
input |
---|
100 10000 5775 6449 -7316 -1958 7663 -52... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 101111111111111111111111111111... |
Test 6
Verdict: ACCEPTED
input |
---|
69 3783 2525 94 604 3228 2004 3034 297... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111110111111111111111111111111... |
Test 7
Verdict: ACCEPTED
input |
---|
100 7 6 -4 5 -3 -2 -7 1 -7 5 -4 6 -1 2 -3 -7 -4 -2 -6 -5 3 1 5 2 6 3 -7 -1 4 ... |
correct output |
---|
SAT 1110001 |
user output |
---|
SAT 1110111 |
Test 8
Verdict: ACCEPTED
input |
---|
100 10000 -4952 -1261 5003 -3310 -4222 -... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111111111111111111111111111111... |
Test 9
Verdict: ACCEPTED
input |
---|
98 9233 -8508 -1216 -293 7691 -1239 -8... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111111111111111111111111111111... |
Test 10
Verdict: ACCEPTED
input |
---|
100 7 1 -5 -1 4 3 -7 -2 -7 3 -4 -5 -3 5 4 7 1 3 -4 6 -5 -1 -4 1 4 3 -5 2 -1 ... |
correct output |
---|
SAT 1011110 |
user output |
---|
SAT 1011111 |
Test 11
Verdict: ACCEPTED
input |
---|
100 10000 9359 -9980 -8247 6762 -1645 -1... |
correct output |
---|
SAT 001110010010111100001111011100... |
user output |
---|
SAT 111011111111111111111111111111... |
Test 12
Verdict: ACCEPTED
input |
---|
86 5516 1198 -4516 -3212 3962 4144 -52... |
correct output |
---|
SAT 000110010000010110101010010001... |
user output |
---|
SAT 111110111111111111111111111111... |
Test 13
Verdict: ACCEPTED
input |
---|
100 7 -2 -5 4 -1 3 -6 7 -5 -1 -4 -6 -7 -2 3 2 -5 6 -3 -7 -1 -4 6 5 4 -3 -7 2 -1 ... |
correct output |
---|
SAT 1011110 |
user output |
---|
SAT 0101111 |
Test 14
Verdict: ACCEPTED
input |
---|
100 10000 -3460 -3462 -859 -6222 -8611 -... |
correct output |
---|
SAT 110000101111101010101011100000... |
user output |
---|
SAT 111111111111111111111111111111... |
Test 15
Verdict: ACCEPTED
input |
---|
51 4584 3076 -1146 2966 -2803 -1829 22... |
correct output |
---|
SAT 110101111110100100111110101011... |
user output |
---|
SAT 111111111111110111101111111111... |
Test 16
Verdict: ACCEPTED
input |
---|
100 7 -7 -3 2 -5 -6 -4 1 -7 -5 -2 -6 1 -3 4 -1 2 -5 3 -6 4 7 4 1 -2 3 7 -5 -6 ... |
correct output |
---|
SAT 1011110 |
user output |
---|
SAT 1111111 |
Test 17
Verdict: ACCEPTED
input |
---|
100 10000 -3664 7325 3898 1141 1345 1792... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111111111111111111111111111111... |
Test 18
Verdict: ACCEPTED
input |
---|
69 3821 -2348 -2894 1432 2685 -2315 -5... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111011111111111011111111111111... |
Test 19
Verdict: ACCEPTED
input |
---|
100 7 -5 3 -7 4 -1 -2 6 -5 1 2 -7 4 6 -3 7 6 1 5 3 4 -2 2 -1 3 7 -5 -6 4 ... |
correct output |
---|
SAT 1011110 |
user output |
---|
SAT 0011111 |
Test 20
Verdict: ACCEPTED
input |
---|
100 10000 5537 9593 -3117 6945 -8883 -16... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111111111111011101111111111111... |
Test 21
Verdict: ACCEPTED
input |
---|
38 7114 -531 4020 606 -1739 3340 1984 ... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111111111111111111111111111110... |
Test 22
Verdict: ACCEPTED
input |
---|
100 7 -1 -2 -3 6 -5 4 -7 6 1 3 7 -5 4 -2 -1 6 -2 -4 -7 -5 -3 7 -6 -1 -4 -5 -3 -2 ... |
correct output |
---|
SAT 0110101 |
user output |
---|
SAT 0110101 |
Test 23
Verdict: ACCEPTED
input |
---|
100 10000 4814 3068 1204 -4824 8362 2537... |
correct output |
---|
SAT 100100010000111111011101010111... |
user output |
---|
SAT 111111111111111111111111111111... |
Test 24
Verdict: ACCEPTED
input |
---|
12 972 237 465 -771 -243 -287 777 -31... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111111011110111111111111111111... |
Test 25
Verdict: ACCEPTED
input |
---|
100 7 -4 2 -6 -7 7 1 4 -4 6 -1 -2 1 -3 7 -3 5 -5 4 1 6 -6 -3 -7 3 5 2 -5 7 ... |
correct output |
---|
SAT 1011110 |
user output |
---|
SAT 0101011 |
Test 26
Verdict: ACCEPTED
input |
---|
100 10000 3823 -9303 -9994 -8088 -5477 5... |
correct output |
---|
SAT 001110010010111100001111011100... |
user output |
---|
SAT 111111111111111011111111101111... |
Test 27
Verdict: ACCEPTED
input |
---|
46 8903 -1276 4005 601 1022 -3390 -454... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111011111111110111111111111111... |
Test 28
Verdict: ACCEPTED
input |
---|
100 7 -7 -1 -3 6 5 4 2 1 3 -4 -5 -2 -6 -7 1 7 -5 -4 3 2 -6 3 -4 -1 2 6 -7 -5 ... |
correct output |
---|
SAT 1000001 |
user output |
---|
SAT 0010111 |
Test 29
Verdict: ACCEPTED
input |
---|
100 10000 -8733 3546 -6093 6994 6990 -80... |
correct output |
---|
SAT 110000101111101010101011100000... |
user output |
---|
SAT 111111111111111111111111111111... |
Test 30
Verdict: ACCEPTED
input |
---|
8 3876 2514 149 1455 1752 3677 -3806 ... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 111111111111111111111111111111... |
Test 31
Verdict: ACCEPTED
input |
---|
100 10 -6 -3 -2 1 4 7 10 -6 1 4 5 7 8 9 -9 -8 -2 1 5 6 7 -9 -4 2 3 5 7 8 ... |
correct output |
---|
SAT 1000111010 |
user output |
---|
SAT 0001001111 |