CSES - KILO 2016 2/5

Submission details
Task:	Lucky-SAT
Sender:	z
Submission time:	2016-09-13 18:45:20 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
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 ...` view save

correct output
`SAT 1011110011` view save

user output
`SAT 0100010000` view save

Test 2

Verdict: ACCEPTED

input
`100 10000 -6030 -8236 5819 -6144 -5929 8...` view save

correct output
`SAT 001110010010111100001111011100...` view save

user output
`SAT 100000001000000000000000000000...` view save

Test 3

Verdict: ACCEPTED

input
`9 7258 -4067 5723 6991 3302 -6175 -41...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000000000000000000000000000...` view save

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 ...` view save

correct output
`SAT 0110101` view save

user output
`SAT 1000000` view save

Test 5

Verdict: ACCEPTED

input
`100 10000 5775 6449 -7316 -1958 7663 -52...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000000000000000000000000000...` view save

Test 6

Verdict: ACCEPTED

input
`69 3783 2525 94 604 3228 2004 3034 297...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000000000000000100100000001...` view save

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 ...` view save

correct output
`SAT 1110001` view save

user output
`SAT 0000000` view save

Test 8

Verdict: ACCEPTED

input
`100 10000 -4952 -1261 5003 -3310 -4222 -...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000000000000010001001000000...` view save

Test 9

Verdict: ACCEPTED

input
`98 9233 -8508 -1216 -293 7691 -1239 -8...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000010000000000000000000001...` view save

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 ...` view save

correct output
`SAT 1011110` view save

user output
`SAT 0011100` view save

Test 11

Verdict: ACCEPTED

input
`100 10000 9359 -9980 -8247 6762 -1645 -1...` view save

correct output
`SAT 001110010010111100001111011100...` view save

user output
`SAT 000000000000000000000000000000...` view save

Test 12

Verdict: ACCEPTED

input
`86 5516 1198 -4516 -3212 3962 4144 -52...` view save

correct output
`SAT 000110010000010110101010010001...` view save

user output
`SAT 000000000100000001100000010100...` view save

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 ...` view save

correct output
`SAT 1011110` view save

user output
`SAT 0101010` view save

Test 14

Verdict: ACCEPTED

input
`100 10000 -3460 -3462 -859 -6222 -8611 -...` view save

correct output
`SAT 110000101111101010101011100000...` view save

user output
`SAT 000000000000000000000000000000...` view save

Test 15

Verdict: ACCEPTED

input
`51 4584 3076 -1146 2966 -2803 -1829 22...` view save

correct output
`SAT 110101111110100100111110101011...` view save

user output
`SAT 000100010000000000100000001000...` view save

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 ...` view save

correct output
`SAT 1011110` view save

user output
`SAT 0000101` view save

Test 17

Verdict: ACCEPTED

input
`100 10000 -3664 7325 3898 1141 1345 1792...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000001000000000000000000000...` view save

Test 18

Verdict: ACCEPTED

input
`69 3821 -2348 -2894 1432 2685 -2315 -5...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000001000000100000000000010000...` view save

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 ...` view save

correct output
`SAT 1011110` view save

user output
`SAT 0011000` view save

Test 20

Verdict: ACCEPTED

input
`100 10000 5537 9593 -3117 6945 -8883 -16...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000000000010000000000000000...` view save

Test 21

Verdict: ACCEPTED

input
`38 7114 -531 4020 606 -1739 3340 1984 ...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000000000000000000000000000...` view save

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 ...` view save

correct output
`SAT 0110101` view save

user output
`SAT 1010010` view save

Test 23

Verdict: ACCEPTED

input
`100 10000 4814 3068 1204 -4824 8362 2537...` view save

correct output
`SAT 100100010000111111011101010111...` view save

user output
`SAT 000000000000000100000000000000...` view save

Test 24

Verdict: ACCEPTED

input
`12 972 237 465 -771 -243 -287 777 -31...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000000000000000001010000000...` view save

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 ...` view save

correct output
`SAT 1011110` view save

user output
`SAT 1010001` view save

Test 26

Verdict: ACCEPTED

input
`100 10000 3823 -9303 -9994 -8088 -5477 5...` view save

correct output
`SAT 001110010010111100001111011100...` view save

user output
`SAT 000000001000000000000000000000...` view save

Test 27

Verdict: ACCEPTED

input
`46 8903 -1276 4005 601 1022 -3390 -454...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000000000000010000000000000...` view save

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 ...` view save

correct output
`SAT 1000001` view save

user output
`SAT 0010010` view save

Test 29

Verdict: ACCEPTED

input
`100 10000 -8733 3546 -6093 6994 6990 -80...` view save

correct output
`SAT 110000101111101010101011100000...` view save

user output
`SAT 000000000000001000000000000000...` view save

Test 30

Verdict: ACCEPTED

input
`8 3876 2514 149 1455 1752 3677 -3806 ...` view save

correct output
`SAT 101111001101011000001011000111...` view save

user output
`SAT 000000000000000000000000000000...` view save

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 ...` view save

correct output
`SAT 1000111010` view save

user output
`SAT 1001100000` view save

KILO 2016 2/5

Lucky-SAT

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Tasks

Submissions (z)