Task: | Lucky-SAT |
Sender: | z |
Submission time: | 2016-09-13 18:45:20 +0300 |
Language: | C++ |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.06 s | details |
#3 | ACCEPTED | 0.05 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.06 s | details |
#6 | ACCEPTED | 0.05 s | details |
#7 | ACCEPTED | 0.06 s | details |
#8 | ACCEPTED | 0.06 s | details |
#9 | ACCEPTED | 0.06 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.05 s | details |
#16 | ACCEPTED | 0.05 s | details |
#17 | ACCEPTED | 0.06 s | details |
#18 | ACCEPTED | 0.05 s | details |
#19 | ACCEPTED | 0.06 s | details |
#20 | ACCEPTED | 0.05 s | details |
#21 | ACCEPTED | 0.05 s | details |
#22 | ACCEPTED | 0.05 s | details |
#23 | ACCEPTED | 0.05 s | details |
#24 | ACCEPTED | 0.05 s | details |
#25 | ACCEPTED | 0.05 s | details |
#26 | ACCEPTED | 0.06 s | details |
#27 | ACCEPTED | 0.05 s | details |
#28 | ACCEPTED | 0.05 s | details |
#29 | ACCEPTED | 0.06 s | details |
#30 | ACCEPTED | 0.05 s | details |
#31 | ACCEPTED | 0.04 s | details |
Code
#include <iostream> #include <set> using namespace std; int n, m; #define SZ (1<<15) int sp[SZ]; multiset<int> k; int cnf[101][7]; set<int> p[20202]; bool ok[10101]; bool u[10101]; bool q[101]; int urm; inline int ABS(int a){return a>=0?a:-a;} void rma(int v){ for (auto a:p[v]){ for (int j=0; j<7; ++j){ if (u[ABS(cnf[a][j])]) continue; p[cnf[a][j]+10101].erase(a); } q[a]=1; --urm; } p[v].clear(); } void rm(int v){ p[v].clear(); } int main(){ cin >> n >> m; for (int i=0; i<n; ++i){ for (int j=0; j<7; ++j){ cin >> cnf[i][j]; p[cnf[i][j]+10101].insert(i); } } urm=n; while (urm){ int mn=1222333444; int mni=-1; for (int i=10101; i<20202; ++i){ if (u[i-10101] ) continue; if (p[i].size() || p[20202-i].size()){ int mnc=min(p[i].size(), p[20202-i].size()); if (mnc<mn){ mn=mnc; mni=i; } } } if (mni==-1){ cout << "UNSAT\n"; return 0; } if (p[mni].size()<p[20202-mni].size()){ rm(mni); rma(20202-mni); }else{ rm(20202-mni); rma(mni); ok[mni-10101]=1; } u[mni-10101]=1; } cout << "SAT\n"; for (int i=1; i<=m; ++i) cout << ok[i]; cout << "\n"; }
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 0100010000 |
Test 2
Verdict: ACCEPTED
input |
---|
100 10000 -6030 -8236 5819 -6144 -5929 8... |
correct output |
---|
SAT 001110010010111100001111011100... |
user output |
---|
SAT 100000001000000000000000000000... |
Test 3
Verdict: ACCEPTED
input |
---|
9 7258 -4067 5723 6991 3302 -6175 -41... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000000000000000000000000000... |
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 1000000 |
Test 5
Verdict: ACCEPTED
input |
---|
100 10000 5775 6449 -7316 -1958 7663 -52... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000000000000000000000000000... |
Test 6
Verdict: ACCEPTED
input |
---|
69 3783 2525 94 604 3228 2004 3034 297... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000000000000000100100000001... |
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 0000000 |
Test 8
Verdict: ACCEPTED
input |
---|
100 10000 -4952 -1261 5003 -3310 -4222 -... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000000000000010001001000000... |
Test 9
Verdict: ACCEPTED
input |
---|
98 9233 -8508 -1216 -293 7691 -1239 -8... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000010000000000000000000001... |
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 0011100 |
Test 11
Verdict: ACCEPTED
input |
---|
100 10000 9359 -9980 -8247 6762 -1645 -1... |
correct output |
---|
SAT 001110010010111100001111011100... |
user output |
---|
SAT 000000000000000000000000000000... |
Test 12
Verdict: ACCEPTED
input |
---|
86 5516 1198 -4516 -3212 3962 4144 -52... |
correct output |
---|
SAT 000110010000010110101010010001... |
user output |
---|
SAT 000000000100000001100000010100... |
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 0101010 |
Test 14
Verdict: ACCEPTED
input |
---|
100 10000 -3460 -3462 -859 -6222 -8611 -... |
correct output |
---|
SAT 110000101111101010101011100000... |
user output |
---|
SAT 000000000000000000000000000000... |
Test 15
Verdict: ACCEPTED
input |
---|
51 4584 3076 -1146 2966 -2803 -1829 22... |
correct output |
---|
SAT 110101111110100100111110101011... |
user output |
---|
SAT 000100010000000000100000001000... |
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 0000101 |
Test 17
Verdict: ACCEPTED
input |
---|
100 10000 -3664 7325 3898 1141 1345 1792... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000001000000000000000000000... |
Test 18
Verdict: ACCEPTED
input |
---|
69 3821 -2348 -2894 1432 2685 -2315 -5... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000001000000100000000000010000... |
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 0011000 |
Test 20
Verdict: ACCEPTED
input |
---|
100 10000 5537 9593 -3117 6945 -8883 -16... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000000000010000000000000000... |
Test 21
Verdict: ACCEPTED
input |
---|
38 7114 -531 4020 606 -1739 3340 1984 ... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000000000000000000000000000... |
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 1010010 |
Test 23
Verdict: ACCEPTED
input |
---|
100 10000 4814 3068 1204 -4824 8362 2537... |
correct output |
---|
SAT 100100010000111111011101010111... |
user output |
---|
SAT 000000000000000100000000000000... |
Test 24
Verdict: ACCEPTED
input |
---|
12 972 237 465 -771 -243 -287 777 -31... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000000000000000001010000000... |
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 1010001 |
Test 26
Verdict: ACCEPTED
input |
---|
100 10000 3823 -9303 -9994 -8088 -5477 5... |
correct output |
---|
SAT 001110010010111100001111011100... |
user output |
---|
SAT 000000001000000000000000000000... |
Test 27
Verdict: ACCEPTED
input |
---|
46 8903 -1276 4005 601 1022 -3390 -454... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000000000000010000000000000... |
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 0010010 |
Test 29
Verdict: ACCEPTED
input |
---|
100 10000 -8733 3546 -6093 6994 6990 -80... |
correct output |
---|
SAT 110000101111101010101011100000... |
user output |
---|
SAT 000000000000001000000000000000... |
Test 30
Verdict: ACCEPTED
input |
---|
8 3876 2514 149 1455 1752 3677 -3806 ... |
correct output |
---|
SAT 101111001101011000001011000111... |
user output |
---|
SAT 000000000000000000000000000000... |
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 1001100000 |