QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#304591#7511. Planar GraphNemanjaSo2005AC ✓3ms4468kbC++147.6kb2024-01-13 21:31:262024-01-13 21:31:27

Judging History

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

  • [2024-01-13 21:31:27]
  • 评测
  • 测评结果:AC
  • 用时:3ms
  • 内存:4468kb
  • [2024-01-13 21:31:26]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,E,K=0;
ll veza[105][105];
struct tacka{
   ll x,y;
   bool operator == (const tacka &a){
      return x==a.x and y==a.y;
   }
   tacka operator - (const tacka &a){
      tacka ret;
      ret.x=x-a.x;
      ret.y=y-a.y;
      return ret;
   }
   tacka operator + (const tacka &a){
      tacka ret;
      ret.x=x+a.x;
      ret.y=y+a.y;
      return ret;
   }
} A[105],B[105];
struct duz{
   tacka p1,p2;
   void fromcords(ll ax,ll ay,ll bx,ll by){
      p1.x=ax;
      p1.y=ay;
      p2.x=bx;
      p2.y=by;
   }
}dpp;
vector<duz> D;
ll znak(ll x){
   if(x==0)
      return 0;
   if(x>0)
      return 1;
   return -1;
}
ll orijent(tacka p1,tacka p2,tacka a){
   if(p1.x==p2.x)
      return znak(p2.y-p1.y)*znak(p1.x-a.x)*-1;
   return (p2.y-a.y)*(p2.x-p1.x)-(p2.x-a.x)*(p2.y-p1.y);
}
bool sekuse(tacka a1,tacka a2, tacka b1,tacka b2){
   if(a1==b1 or a1==b2 or a2==b1 or a2==b2)
      return false;
   if(znak(orijent(a1,a2,b1))==znak(orijent(a1,a2,b2)))
      return false;
   if(znak(orijent(b1,b2,a1))==znak(orijent(b1,b2,a2)))
      return false;
   return true;
}
void dodajduz(tacka a,tacka b){
   duz d;
   d.p1=a;
   d.p2=b;
   D.push_back(d);
}
bool seceneku(duz x){
   for(ll i=0;i<D.size();i++)
      if(sekuse(x.p1,x.p2,D[i].p1,D[i].p2)){
        /* cout<<"SEKU SE "<<x.p1.x<<" "<<x.p1.y<<" ";
         cout<<x.p2.x<<" "<<x.p2.y<<" ";
         cout<<D[i].p1.x<<" "<<D[i].p1.y<<" ";
         cout<<D[i].p2.x<<" "<<D[i].p2.y<<endl;*/
         return true;
      }
   return false;
}
struct troug{
   ll a,b,c;
   vector<ll> sused;
   bool tacka;
} niz[10005];
bool sused(troug x,troug y){
   vector<ll> ist;
   if(x.a==y.a) ist.push_back(x.a);
   if(x.a==y.b) ist.push_back(x.a);
   if(x.a==y.c) ist.push_back(x.a);
   if(x.b==y.a) ist.push_back(x.b);
   if(x.b==y.b) ist.push_back(x.b);
   if(x.b==y.c) ist.push_back(x.b);
   if(x.c==y.a) ist.push_back(x.c);
   if(x.c==y.b) ist.push_back(x.c);
   if(x.c==y.c) ist.push_back(x.c);
   if(ist.size()<2)
      return false;
   //cout<<"ISTI "<<ist[0]<<" "<<ist[1]<<endl;
   return veza[ist[0]][ist[1]]==1;
}
pair<ll,ll> edg[305];
vector<ll> ima[105][105];
bool gduz(ll a,ll b, bool upit){
   if(veza[a][b]==2 and upit)
      return false;
   tacka p1=A[a];
   tacka p2=A[b];
   ll kol[3]={0,0,0};
   for(ll i=1;i<=N;i++){
     // cout<<znak(orijent(p1,p2,A[i]))<<endl;
      kol[1+znak(orijent(p1,p2,A[i]))]++;
   }
   //cout<<"KRAJ"<<endl;
   if(kol[0]==0 or kol[2]==0)
      return true;
   return false;
}
void dfs(ll gde){
   if(niz[gde].tacka)
      return;
   //cout<<"DFS "<<gde<<endl;
   niz[gde].tacka=true;
   for(ll i=0;i<niz[gde].sused.size();i++)
      dfs(niz[gde].sused[i]);
   return;
}
bool cmp(tacka a,tacka b){
   if(a.x<b.x)
      return true;
   if(a.x>b.x)
      return false;
   return a.y<b.y;
}
bool pripada(troug T,tacka P){
   tacka niz[3]={A[T.a],A[T.b],A[T.c]};
   sort(niz,niz+3,cmp);
   ll orj=znak(orijent(niz[0],niz[1],P));
  // cout<<"PRIPADA LI"<<endl;
 //  cout<<niz[0].x<<" "<<niz[0].y<<" "<<niz[1].x<<" "<<niz[1].y<<" "<<niz[2].x<<" "<<niz[2].y<<" "<<endl;
 //  cout<<P.x<<" "<<P.y<<endl;
 //  cout<<orijent(niz[0],niz[1],P)<<" "<<orijent(niz[1],niz[2],P)<<" "<<orijent(niz[2],niz[0],P)<<endl;
   if(orj!=znak(orijent(niz[1],niz[2],P)))
      return false;
   if(orj!=znak(orijent(niz[2],niz[0],P)))
      return false;
 //  cout<<"DA"<<endl;
   return true;
}
int main(){
   /*while(true){
      ll a,b,c,d;
      tacka a1,a2,b1,b2;
      cin>>a1.x>>a1.y;
      cin>>a2.x>>a2.y;
      cin>>b1.x>>b1.y;
      cin>>b2.x>>b2.y;
      cout<<sekuse(a1,a2,b1,b2)<<endl;
   }*/
   cin>>N>>M>>E;
   for(ll i=1;i<=N;i++){
      cin>>A[i].x>>A[i].y;
   }
   for(ll i=1;i<=M;i++){
      cin>>B[i].x>>B[i].y;
   }
   ll a,b;
   for(ll it=1;it<=E;it++){
      cin>>a>>b;
      if(a>b)
         swap(a,b);
      veza[a][b]=2;
      veza[b][a]=2;
      dodajduz(A[a],A[b]);
      edg[it]={a,b};
   }
   for(ll i=1;i<=N;i++)
      for(ll j=i+1;j<=N;j++){
         if(veza[i][j])
            continue;
         duz d;
         d.p1=A[i];
         d.p2=A[j];
         if(seceneku(d))
            continue;
         D.push_back(d);
        // cout<<"DODAJEM "<<i<<" "<<j<<endl;
         veza[i][j]=1;
         veza[j][i]=1;
      }
   for(ll a=1;a<=N;a++)
      for(ll b=a+1;b<=N;b++)
         for(ll c=b+1;c<=N;c++){
            if(!veza[a][b])
               continue;
            if(!veza[a][c])
               continue;
            if(!veza[b][c])
               continue;
            bool dobar=true;

            for(ll it=1;it<=N;it++){
               if(it==a or it==b or it==c)
                  continue;
               troug T;
               T.a=a;
               T.b=b;
               T.c=c;
               if(pripada(T,A[it])){
                  dobar=false;
                 // cout<<"PRIPADA "<<A[it].x<<" "<<A[it].y<<endl;
                  break;
               }
            }
            if(!dobar)
               continue;

           // cout<<"DOBAR"<<endl;
            K++;
      //      cout<<"TROUGAO "<<K<<":   "<<a<<" "<<b<<" "<<c<<endl;
            niz[K].a=a;
            niz[K].b=b;
            niz[K].c=c;

            ima[a][b].push_back(K);
            ima[b][a].push_back(K);

            ima[a][c].push_back(K);
            ima[c][a].push_back(K);

            ima[b][c].push_back(K);
            ima[c][b].push_back(K);
         }

   for(ll i=1;i<=E;i++){
      ll a=edg[i].first;
      ll b=edg[i].second;
    /*  cout<<a<<" "<<b<<endl;
      for(ll j=0;j<ima[a][b].size();j++)
         cout<<ima[a][b][j]<<" ";
      cout<<endl<<endl;*/
   }
   //cout<<K<<endl;
   for(ll i=1;i<=K;i++)
      for(ll j=i+1;j<=K;j++)
         if(sused(niz[i],niz[j])){
            niz[i].sused.push_back(j);
            niz[j].sused.push_back(i);
            //cout<<"SUSEDI "<<i<<" "<<j<<endl;
         }
   for(ll i=1;i<=K;i++){
      bool gran=false;
    //  cout<<i<<endl;
      gran|=gduz(niz[i].a,niz[i].b,true);
     // cout<<gran<<" ";
      gran|=gduz(niz[i].a,niz[i].c,true);
     // cout<<gran<<" ";
      gran|=gduz(niz[i].b,niz[i].c,true);
    //  cout<<gran<<endl;
      if(gran){
         niz[i].sused.push_back(K+1);
         niz[K+1].sused.push_back(i);
      //   cout<<"SUSEDI "<<i<<" "<<K+1<<endl;
      }
   }
  /* cout<<"SUSEDI: "<<endl;
   for(ll i=1;i<=N;i++){
      cout<<i<<": ";
      for(ll p:niz[i].sused)
         cout<<p<<" ";
      cout<<endl;
   }
*/

   for(ll i=1;i<=K;i++)
      for(ll j=1;j<=M;j++)
         if(pripada(niz[i],B[j])){
            dfs(i);
           // cout<<"IMA "<<i<<endl;
         }

   bool post=false;
   for(ll i=1;i<=M;i++){
     // cout<<i<<endl;
      bool dob=true;
      for(ll j=1;j<=K;j++){
      //   cout<<j<<" "<<pripada(niz[j],B[i])<<endl;
         if(pripada(niz[j],B[i]))
            dob=false;
      }
      post|=dob;
   }
   if(post)
      dfs(K+1);

   for(ll i=1;i<=E;i++){
      ll a=edg[i].first;
      ll b=edg[i].second;
      ll ans=0;
      for(ll j=0;j<ima[a][b].size();j++)
         if(niz[ima[a][b][j]].tacka)
            ans=1;
      if(gduz(a,b,false) and niz[K+1].tacka)
         ans=1;
      cout<<ans;
   }
   cout<<endl;
   return 0;
}

/*
10 1 14

-1 8
0 4
4 6
7 3
5 0
2 0
5 3
-3 -2
9 -1
9 8

3 2

1 2
1 8
2 3
2 7
3 4
3 7
4 5
5 6
5 7
8 9
9 10
3 10
10 1
2 8
*/
/*
12 2 13
0 6
2 5
1 2
2 0
3 1
6 1
6 3
7 6
7 9
4 9
5 5
3 4

5 7
2 3

1 2
2 3
2 12
3 4
3 5
5 7
5 12
6 7
7 8
8 9
8 10
10 11
11 12
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 4260kb

input:

4 1 3
-2 0
0 2
2 0
0 1
0 3
1 2
2 3
1 3

output:

111

result:

ok single line: '111'

Test #2:

score: 0
Accepted
time: 1ms
memory: 4320kb

input:

13 35 13
13 12
16 -3
18 4
4 -7
23 -22
9 -23
23 11
12 -1
19 -5
15 -15
5 -15
-17 11
-17 -13
-20 19
11 -12
-10 14
-3 14
7 -4
-10 -23
-19 -12
-13 1
-22 10
-21 -1
18 -9
-8 1
13 22
12 -23
-9 -9
-12 -20
4 -3
-6 17
14 -10
10 13
-5 -2
-4 -12
13 22
-18 -21
19 5
12 -18
4 0
3 -17
5 -2
-2 0
8 0
-8 1
14 -18
3 -9
...

output:

1111111111111

result:

ok single line: '1111111111111'

Test #3:

score: 0
Accepted
time: 2ms
memory: 4436kb

input:

68 59 168
51 -57
-26 -51
-31 58
-45 -78
-46 -49
-53 14
76 -69
-64 32
58 -49
-1 12
-65 28
-15 -10
29 -53
25 -32
78 -41
24 -37
69 56
54 -10
3 36
-18 46
53 -30
41 -2
-30 13
-58 -37
-20 42
-48 -38
-42 22
64 0
9 -56
7 -11
-66 -23
19 -9
-26 -6
-61 -68
57 13
-13 50
-15 -11
-77 47
-77 57
78 51
-37 56
-75 24...

output:

011111111111111111100001011000001001110111110111101011011001111110011011101111110111011101001000000001010100111111100110000100110100101101111111110011001111111100100011

result:

ok single line: '011111111111111111100001011000...1111111110011001111111100100011'

Test #4:

score: 0
Accepted
time: 1ms
memory: 4428kb

input:

59 1 158
-51 8
50 48
-56 -67
19 7
33 -47
32 44
42 47
-36 -57
15 34
-8 23
-24 43
20 11
61 -41
58 -11
-68 -45
36 -54
-21 42
-28 -49
-28 -31
-34 20
29 -65
-13 38
-22 -36
-30 11
-40 57
64 -69
65 51
47 34
-41 31
-1 35
28 -11
58 58
13 12
-52 43
40 6
46 48
46 -59
-52 30
69 -23
-34 38
-1 -5
-12 -27
-11 24
-...

output:

00000000000000000000000000000000000000000000000000000000000001000000000000000000000000000001000000000000000000000000000000000000000000000000001000000000000000

result:

ok single line: '000000000000000000000000000000...0000000000000001000000000000000'

Test #5:

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

input:

92 1 125
55 10
67 -85
-26 80
36 -32
44 -64
41 -50
-93 -80
-66 -92
-68 27
-79 9
87 -61
-40 -64
89 100
75 -42
59 40
60 -30
-66 27
63 90
-19 100
24 -20
-13 83
-100 -92
-83 58
-33 -70
74 -20
-55 73
-41 28
27 -31
-37 -22
40 18
-3 -2
70 79
71 29
32 -73
39 -1
17 -95
-61 56
94 -10
-79 -66
-84 87
-16 71
52 4...

output:

10010010000101001010010100101100100000001010001000000001101111101000011111000000001011000100000010100000000100011011000000110

result:

ok single line: '100100100001010010100101001011...0010100000000100011011000000110'

Test #6:

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

input:

85 47 204
48 93
-32 10
71 70
-37 10
20 -12
-32 -56
1 -22
-46 -64
56 82
-19 63
-5 83
16 89
79 81
51 -22
43 59
33 -87
28 67
-18 38
-16 -23
18 -78
87 66
-83 29
36 58
6 -2
68 80
18 -34
-17 59
-31 -12
-37 -75
33 -79
-51 -24
-88 6
-19 62
71 -78
-51 72
-49 -45
21 41
-58 33
46 67
-11 -31
62 46
54 55
37 -14
...

output:

000110010001001101100010110101100100011110011110110101010100110011111010101110101001001011100000110101000100010011100100100110100001011010001010001010000100011000001101010110011001101111010000011001000011

result:

ok single line: '000110010001001101100010110101...0011001101111010000011001000011'

Test #7:

score: 0
Accepted
time: 2ms
memory: 4396kb

input:

59 96 152
-75886847 147807525
335545968 317138952
262969730 -308175740
91308409 -162085508
-397786268 -191693417
-227565597 195627938
45666011 253210394
-311142459 58197832
-412164189 -270215767
-12639523 -314154358
-269901472 -366179516
-306681757 -167771007
194329800 -339296479
-12501616 -15788817...

output:

01110111111111111110101110111011101111110011100110100111110110001110111101100111100111010111111110110101110111110011111001110001111100010111110111111111

result:

ok single line: '011101111111111111101011101110...1110001111100010111110111111111'

Test #8:

score: 0
Accepted
time: 1ms
memory: 4368kb

input:

62 1 99
-72 -45
-58 -44
-39 5
-45 -56
11 -26
-7 56
-29 -56
-70 -26
64 -64
-12 6
4 44
-14 68
-28 29
-68 -52
-21 -10
19 -37
17 -30
26 64
-40 2
-11 -30
64 -45
38 -67
43 -35
67 -49
50 72
-60 -2
-28 37
55 55
-7 42
-63 -32
71 35
-55 26
-67 -49
-42 -43
69 59
-29 5
0 -36
-1 8
-53 66
1 -6
-2 32
-51 -61
-27 6...

output:

000010000000000110001101000110000000010010000001001001100000010010000010001100010011010101001000010

result:

ok single line: '000010000000000110001101000110...0010001100010011010101001000010'

Test #9:

score: 0
Accepted
time: 1ms
memory: 4324kb

input:

63 1 175
50549954 -224104196
-187903718 57327090
-61398050 89271831
72686467 -167765054
4226095 73332567
-80682032 -158732552
-366425325 -180661648
-210787891 -107411752
44235201 233049038
-29484914 -280845598
228925315 -106736012
-169221325 64453690
-127160591 78410226
374001485 -312357450
31528300...

output:

0000000100000000000000000000000000010000000000000000000001000000000000000010000000000000000000000000000000000010000000000000010000000000000001000000000100000101000000000001000

result:

ok single line: '000000010000000000000000000000...0000000100000101000000000001000'

Test #10:

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

input:

82 4 66
182782804 77923360
117828203 139218692
-110620000 89777361
273011388 138341008
294610527 -194481138
294204618 -290402347
194417551 48839146
-161919200 -261350494
-260772975 -239789170
117370125 245536520
-201599590 -82451402
291486591 84106590
296266013 309943147
-220542664 54399074
24021444...

output:

111101011111111111111111010111111101010111100110100011111111011111

result:

ok single line: '111101011111111111111111010111...1010111100110100011111111011111'

Test #11:

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

input:

65 50 147
-581452360 190355182
-642896619 -572084384
-305018177 -539060586
-328404608 -74526018
198824769 -402666976
-604806291 420433161
646918331 -591294299
360443372 -456307852
253325248 -341024549
-656241212 302363402
524405246 -499973260
-531933602 617077471
-185233072 -318131117
-362315669 -49...

output:

011111111110100110100010010101111011110111010001101101001001111101111111011011011001001001101100100111110111001101101010100100110111100110101010100

result:

ok single line: '011111111110100110100010010101...1010100100110111100110101010100'

Test #12:

score: 0
Accepted
time: 2ms
memory: 4336kb

input:

71 1 142
26 16
-81 21
53 -64
-46 67
-37 73
46 79
66 -27
46 53
38 -44
16 44
-44 -43
-8 -30
65 12
60 2
-26 -24
7 71
-31 -27
-13 0
-80 80
77 -65
71 2
8 -53
-64 -71
52 -58
30 53
61 -18
56 -34
-80 -13
80 56
-28 -79
-43 -52
-38 77
11 -1
-30 -73
-39 30
-61 69
-41 66
16 -45
40 -51
37 40
-26 34
57 29
-15 -8
...

output:

1000000100000100000000001001000000000010101000000100000011001000000000000001000000000000000000000000000000000000000010011000000000000000000010

result:

ok single line: '100000010000010000000000100100...0000010011000000000000000000010'

Test #13:

score: 0
Accepted
time: 2ms
memory: 4468kb

input:

88 68 244
452074073 749836590
-422267242 -370342423
-649645359 303851355
285738514 -585228292
674035872 344344527
-564943027 45741258
301794983 564572022
349063999 218051130
668851769 598897930
596201080 -750109936
95583385 363387733
130300372 -350613210
-126422550 -684185703
-117024972 -406661982
-...

output:

1111011101010010110011001011101101100000000010100110001111000010001011100110001100101100000010001011101100010000010110111000010101010100101011011101011010011110000111010000011110110111101110011111001111101000110001000110101101001101111100111101

result:

ok single line: '111101110101001011001100101110...1000110101101001101111100111101'

Test #14:

score: 0
Accepted
time: 1ms
memory: 4352kb

input:

24 47 58
-536382548 -36211682
-617682678 630246425
-680303961 -753887401
-576626558 -547501154
-166237320 -247093489
-780629487 -564369462
745821462 -462233962
-29960131 -120134355
-215230222 568441689
-505349805 471834374
-268168811 -773902784
-436226654 -153342090
-686102938 -414449668
-318346027 ...

output:

1011111110101111101111111011101111100110100110101011111011

result:

ok single line: '1011111110101111101111111011101111100110100110101011111011'

Test #15:

score: 0
Accepted
time: 2ms
memory: 4416kb

input:

76 82 181
-835091273 636197461
-809826661 -915012307
-514114180 762992620
-801978217 -646901746
-937647819 -73101245
632623370 -798225996
-949969476 -45929520
677089833 -491546441
-818746494 -457407341
-23609804 -63980274
927682282 -371416961
-936340868 -741789992
-82906350 -740214368
-884276937 -32...

output:

1011111111110100011011111001011110100011001111111001011100111111111110011100101011101011101011111011001100001001110001101110010010101111000101010100111100011011110001100110110110011

result:

ok single line: '101111111111010001101111100101...1100011011110001100110110110011'

Test #16:

score: 0
Accepted
time: 2ms
memory: 4416kb

input:

95 1 39
1 -2
5 -59
6 23
77 57
87 -81
96 -9
20 45
-41 5
-80 -76
62 -83
-26 93
89 -61
-104 -65
55 4
50 55
61 -39
-26 -18
-90 -98
-14 38
56 -61
-100 105
92 -4
30 -98
-13 -27
-21 27
-49 95
62 20
91 24
-75 -30
68 -4
-86 84
-17 -13
-93 13
-38 -64
40 -82
63 47
-9 28
-95 7
91 -51
-50 -66
54 27
-3 -12
-8 -89...

output:

110111101111111110111011111111111111111

result:

ok single line: '110111101111111110111011111111111111111'

Test #17:

score: 0
Accepted
time: 1ms
memory: 4372kb

input:

53 1 95
249310291 444009281
-51319591 -127058272
-521364452 184610945
-21697253 -380031119
-765296404 788815734
480089046 -792178676
285516793 131912022
715950950 -65482217
36211136 -559456984
-46323546 622669323
812068024 -71601366
-6695845 -158750172
23940379 638024824
-792521738 -179875992
-72088...

output:

00000000000010000100000000000100000000000000000000000000000000000000000100000000000000000000000

result:

ok single line: '000000000000100001000000000001...0000000100000000000000000000000'

Test #18:

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

input:

90 87 67
-37 -98
66 -40
17 24
-32 51
-68 56
-47 78
-83 66
-16 -22
41 -12
-31 86
-1 11
42 65
-27 2
-19 -21
-54 78
-14 -77
-74 5
-46 82
-19 63
76 43
-39 -7
62 -49
68 4
-26 72
-91 0
-40 -74
9 -68
92 64
21 88
53 -55
32 -12
100 -26
9 -24
43 -93
-99 19
-76 -3
21 97
-57 -92
-28 26
-10 -95
96 -11
43 -82
22 ...

output:

1111111111111111111111111111110111111111111111111111111111111111111

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #19:

score: 0
Accepted
time: 1ms
memory: 4332kb

input:

27 42 12
-196639452 -910071469
556979079 -24132720
-907504137 -798429714
217201737 894945050
592735402 -891961813
351726786 -961077191
428253659 -337157490
-814353097 482187973
-746163779 14512669
-639377173 -925754520
-499592664 319782459
-500528351 591167527
-701230268 -495398846
-836405665 445706...

output:

111111111111

result:

ok single line: '111111111111'

Test #20:

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

input:

63 28 102
-65 69
73 -1
0 -30
-69 -66
48 39
3 -37
52 26
13 18
19 -61
-9 54
24 30
-62 58
-64 -64
-6 -3
48 -24
-58 -59
-45 -1
19 -44
64 13
69 -31
38 13
73 -50
-7 -43
4 58
38 56
-21 36
-36 40
-73 17
23 63
-18 63
41 14
47 68
-16 -47
-30 61
-33 43
-45 25
-31 22
-42 2
1 -40
-17 -2
-65 6
21 -58
31 -15
3 -50...

output:

011111100111111110111110011111010010001111111101100111011111111011110101110101011001111111011111111010

result:

ok single line: '011111100111111110111110011111...1110101011001111111011111111010'

Test #21:

score: 0
Accepted
time: 2ms
memory: 4464kb

input:

81 70 214
501181684 467604004
467393962 79858372
-24971604 -76855555
310835183 -451578432
529058882 -371153027
10117013 439009502
-102203223 498873755
104983339 -167287519
-234656041 548196249
-355162848 -403411047
-303715296 -31203991
412378489 -143945211
-38540379 -474967805
-321224760 115499601
-...

output:

0010100000110011101001110011111111000011110110011000110000111111000110011111000001000100111000101111110111101011101110100000001101010100110100011011111111000100110110010100010001101111000101110110010110011010110000

result:

ok single line: '001010000011001110100111001111...1000101110110010110011010110000'

Test #22:

score: 0
Accepted
time: 1ms
memory: 4240kb

input:

2 1 0
-381381789 -155480688
476986136 269997025
374524257 360034879

output:



result:

ok 0 lines

Test #23:

score: 0
Accepted
time: 2ms
memory: 4320kb

input:

64 98 165
368476226 -245975441
321964920 84032145
168655443 132633922
191654925 58795031
174065240 -211635910
349833228 30545690
200179574 272085215
100336543 -391757623
172093450 34273303
-393548578 392781830
-335701529 189217228
-23681938 -213109493
-337162597 334472127
-11931889 167942850
9961263...

output:

111111010111111101101110011011111111011001110111111001000111110111111011110011010101111101101111101101101111011111111101100001010011101101100111100111011100111101100

result:

ok single line: '111111010111111101101110011011...1101100111100111011100111101100'

Test #24:

score: 0
Accepted
time: 1ms
memory: 4412kb

input:

48 3 106
-11919288 401311957
-300306784 -473247000
-572232580 -129053552
-253134521 21856503
-435640199 -269285358
28497548 154734438
449368223 254505621
-41113963 -73600818
-445437245 -234603342
-434722859 -577811918
-411116809 140213809
188703595 -442513896
-200064854 -383148625
-278682300 2351034...

output:

0000000000001000000100000010100000110110000000000010010000010000001000000000000010100000100000000000100000

result:

ok single line: '000000000000100000010000001010...0000010100000100000000000100000'

Test #25:

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

input:

32 67 68
-36 -20
2 9
34 -32
-29 -5
-31 25
37 -29
42 -31
11 40
-33 9
8 -5
-16 -11
-18 -8
8 36
2 20
22 6
-32 4
-3 -30
-18 -34
42 40
-40 -40
-19 -12
-33 30
-34 17
-39 -6
26 -29
41 -19
17 -18
-34 -41
37 -7
32 7
-6 -23
-16 29
14 36
-21 32
-21 -28
-30 40
-21 13
-38 3
37 -31
-2 -8
5 5
36 -37
-35 16
38 33
-...

output:

11011111111010110111111111111100101111111111011011011111111111111111

result:

ok single line: '110111111110101101111111111111...1111111011011011111111111111111'

Test #26:

score: 0
Accepted
time: 1ms
memory: 4284kb

input:

40 1 72
-3372678 23575085
-14527803 -22685257
-5770297 10287106
15480880 -9727089
-13598905 -11137818
-23830038 -22435224
-16870142 11247699
22240990 -4980969
19912096 1617242
8897796 -1011804
20884847 -13905376
1075116 -18515777
-24742774 -21603292
-17315892 17920458
3074471 2211097
-19379610 -1295...

output:

000000000001000000000000000000000010001000001000000000000000000000000000

result:

ok single line: '000000000001000000000000000000...0001000000000000000000000000000'

Test #27:

score: 0
Accepted
time: 3ms
memory: 4452kb

input:

100 1 161
-80137690 25887305
-112675497 -60746940
113490133 75503508
61659499 44746640
-14968017 -100091877
-104246751 105396818
84695481 27512974
26707762 30557205
-50252976 43123976
-87452977 -114609404
-90960888 -29046502
56406267 47388462
31699712 -101291314
-68208465 -106761143
-67054841 -66583...

output:

00001000000001000000000000000000100000000000000001000100110000010001000000001000100110100000010000010000001000000101000101000000100001010000001000000001010000100

result:

ok single line: '000010000000010000000000000000...0001010000001000000001010000100'

Test #28:

score: 0
Accepted
time: 2ms
memory: 4388kb

input:

53 1 47
-60 21
-8 13
32 -28
58 -7
-43 5
-18 7
42 23
35 22
-59 16
20 -17
-55 -25
-62 -47
-18 -42
61 14
53 -34
-51 -60
-50 -18
37 58
-26 14
-59 59
-51 24
-43 -46
-47 27
27 -15
-26 26
-7 -50
40 -2
-57 -1
-37 25
27 1
44 16
25 50
47 32
-42 40
-49 9
37 45
-32 31
61 44
14 21
-25 -18
33 47
-33 -11
34 36
-45...

output:

00000100001000000000000000000000000000000000110

result:

ok single line: '00000100001000000000000000000000000000000000110'

Test #29:

score: 0
Accepted
time: 1ms
memory: 4328kb

input:

62 1 97
-288124496 55427633
-106217896 -320441624
412921225 229817207
-275224721 -519311403
325626455 17792730
694140 -370700355
221344845 -292576453
278441135 91382191
-264581148 605253608
288040649 -257804861
565015276 321207185
-376426170 -97185967
-275609526 177082714
165378518 509619762
-289226...

output:

0000011010101001100001000001010001010000000000010010000011100000000110000101010000010001000000100

result:

ok single line: '000001101010100110000100000101...0110000101010000010001000000100'

Test #30:

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

input:

60 40 102
31 60
62 -5
-59 -14
-14 69
30 21
-40 43
18 4
-12 -14
-41 -46
24 -12
23 39
15 -5
-57 -47
34 -26
53 -55
-63 49
-17 -26
60 -35
42 -22
-32 -47
4 31
18 38
-56 -49
70 41
46 34
-8 39
30 -24
-69 -66
-10 -62
28 -38
11 0
12 25
-30 7
52 29
68 -3
-58 -28
3 0
57 -69
-40 62
51 53
-68 -44
58 -25
-36 -49
...

output:

111111110010111111111100100111001111101111101111110100110010011111111101001101101011100111111111010111

result:

ok single line: '111111110010111111111100100111...1001101101011100111111111010111'

Test #31:

score: 0
Accepted
time: 1ms
memory: 4296kb

input:

38 1 88
-446400801 -432601444
199781326 451912811
-310982031 -352396254
-371451563 446705858
-455182293 -115870523
192342741 -247378438
52021139 -157133935
425618795 81760805
-289321740 73826020
237967642 245405012
139542786 408639766
-383554281 -393726138
-242304554 230654135
180115969 -217593842
-...

output:

0000001000000000000001000000000000000000000000000000000001000000000000000000000000000000

result:

ok single line: '000000100000000000000100000000...1000000000000000000000000000000'

Test #32:

score: 0
Accepted
time: 2ms
memory: 4372kb

input:

76 1 203
-114230262 198639426
-233519874 304535156
71925374 17384831
61187577 -239527087
-1301445 -284823715
-17528795 -87694527
-71891668 -87551507
297990011 72199440
298333978 -166850097
-217459867 241758763
182666664 130453342
-45491109 -127986422
-66978149 -250733511
302411526 -274384662
1224861...

output:

00000000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000001000000000000000

result:

ok single line: '000000000000000010000000000000...0100000000000001000000000000000'

Test #33:

score: 0
Accepted
time: 1ms
memory: 4328kb

input:

25 1 15
-3 34
21 -21
26 -8
-35 16
-16 -6
24 17
-29 7
0 27
-16 30
33 30
31 2
-25 25
31 33
-10 -22
-25 5
-32 11
-6 2
-35 -3
4 -18
8 -23
32 -28
26 26
-20 -3
-18 -17
20 19
-7 -34
4 8
20 23
12 13
8 21
6 13
4 16
13 21
8 11
5 18
6 11
2 19
7 8
5 14
7 16
6 25

output:

111111111111111

result:

ok single line: '111111111111111'

Test #34:

score: 0
Accepted
time: 2ms
memory: 4336kb

input:

69 1 60
59116022 108407
94778844 -122980783
41883194 19636800
-187451713 6187507
-20192750 220459924
-20310470 -194332991
60290065 186874427
117664759 -156393226
5968406 70428711
85377868 168601959
-121623776 -10805246
-142624509 79757169
35682197 -40150966
143098357 -84077220
201596816 128462146
-1...

output:

110000000011000000000010000000000010000000000000000000000000

result:

ok single line: '110000000011000000000010000000000010000000000000000000000000'

Test #35:

score: 0
Accepted
time: 1ms
memory: 4300kb

input:

50 80 107
-136821224 438342159
-418706353 9399993
227086984 708880509
-699325397 650928735
-683886486 -542763048
445537952 437994317
-547883573 -612772235
674767503 301331010
711167575 -504002762
-302413612 585767673
-617012243 -579675418
436969684 -389018306
-176369404 -556177193
199740497 -1279731...

output:

11101001110110011111011110101111111101110111111101011111011011001110111110101110111110110110010101111111111

result:

ok single line: '111010011101100111110111101011...1110111110110110010101111111111'

Test #36:

score: 0
Accepted
time: 1ms
memory: 4400kb

input:

27 1 64
-25051747 96640487
11315454 -51389072
95068722 16273286
-22843851 -70513190
-74137758 -9111615
21053920 -107867712
-32614318 103549910
2393150 19168515
-90542955 -54660103
-13312789 63595983
-8635454 74271767
100997992 7975546
42195819 121435672
-33155278 68709317
-6510510 -64937636
55899006...

output:

0000000000001000000000000000010000000100000100001000000000010100

result:

ok single line: '0000000000001000000000000000010000000100000100001000000000010100'

Test #37:

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

input:

23 1 18
-587851478 132420486
-475758602 -400608037
-98931454 -551980136
-340511412 -276505996
-83836150 55454149
-54179724 206559858
-455797934 -154251228
464412902 39052879
301564372 -401006721
-546638191 425633896
-186653938 573749346
134221719 588337034
-70138896 -525202115
-327528605 540665503
2...

output:

011011111111111110

result:

ok single line: '011011111111111110'

Test #38:

score: 0
Accepted
time: 2ms
memory: 4312kb

input:

52 38 52
-172741511 530619780
549977080 474404309
-547915702 438421321
-391365339 34163364
548153306 -519024791
-180235574 347572036
-163100589 273868723
-425058097 56352201
-43670197 -199317783
183157655 -212775074
248267302 322744067
147359299 445994893
-44259658 -345348250
27220688 248380193
4262...

output:

1111111111111111111111111111111111111111111111111111

result:

ok single line: '1111111111111111111111111111111111111111111111111111'

Test #39:

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

input:

84 1 188
76 61
65 15
80 83
-94 -27
92 29
-27 29
-23 -64
-92 53
8 -82
-28 44
-72 1
-65 -60
61 -35
-85 14
-58 80
-71 -63
26 -51
54 -57
4 19
45 0
22 59
-25 -32
-57 -11
20 -76
-31 46
78 -7
23 76
10 -37
1 23
1 6
-88 -16
-43 56
-49 27
73 -48
77 66
58 -27
38 89
25 87
51 44
47 -59
21 -20
-5 -67
23 -89
32 -2...

output:

00000000001000001001000000000010000000000001001000000000010001000000001001000000010000000000000000000000001100000000010010000000000000000000000000000000000000000000000000000000000000100000

result:

ok single line: '000000000010000010010000000000...0000000000000000000000000100000'

Test #40:

score: 0
Accepted
time: 2ms
memory: 4376kb

input:

100 1 151
113561380 110916055
-202042971 210205642
12303413 111952262
28581056 84194411
205637761 181102235
156312466 137951229
118778185 -93636318
-119495509 -134216633
206600413 166496494
196542187 199300725
-224152338 86716607
28676325 -214678702
-73145624 -46988839
-118078074 138104323
-28028396...

output:

0000000100000000000001000000000010000000000000000001000000000000000100000000001000000000000000000000000000000000000000101000000000000000000000000000000

result:

ok single line: '000000010000000000000100000000...1000000000000000000000000000000'

Test #41:

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

input:

12 84 12
-36439905 31935320
-68591283 13528537
-36821752 -10120895
-23268663 -51987362
-17270332 27599642
-14220756 66133940
4217801 -58637875
20311027 52760847
-672927 -20784000
-42946290 64478308
45462745 -2041480
-32664304 -62771948
69287632 -42291606
12112366 24444326
17494701 -24483473
29503643...

output:

111111111111

result:

ok single line: '111111111111'

Test #42:

score: 0
Accepted
time: 1ms
memory: 4368kb

input:

52 14 42
45 18
0 45
-30 21
53 35
-59 2
21 -16
-24 -62
-48 -49
38 -6
46 -18
33 -53
11 -17
-15 61
3 45
-45 -6
49 20
50 -25
48 -57
-39 11
-46 43
24 -20
-33 -43
52 -29
23 -12
48 53
-20 -16
-44 -46
57 -41
16 -19
-52 -37
4 42
10 -48
31 21
-45 -62
-8 -39
21 -11
7 10
25 33
2 49
12 25
16 48
-39 43
-58 -34
-4...

output:

111111111111111111111111111111111111111111

result:

ok single line: '111111111111111111111111111111111111111111'

Test #43:

score: 0
Accepted
time: 1ms
memory: 4344kb

input:

13 1 11
50001509 48881161
-59857365 30669626
54162135 62601120
-12056654 -29581450
20555084 -37862653
-64440885 65834270
41954171 -10072075
-10372539 -12139482
-61460535 -47231591
-14493051 -29020806
-48650146 45492863
18452711 14049436
39478906 -44669995
-59830633 -32027973
6 12
3 13
12 13
5 12
10 ...

output:

11101110111

result:

ok single line: '11101110111'

Test #44:

score: 0
Accepted
time: 2ms
memory: 4388kb

input:

78 1 121
396995327 158214181
415024439 -659811167
448527806 154062383
208165138 -391842000
193474414 -134150962
-323390941 -175627012
-731206356 -703653906
328435642 42666595
448320717 -192428896
-179674960 -193976132
150468115 -152990895
-169233627 -649281727
-329098117 691631973
-733457437 -610681...

output:

0010000000000000000001000000000000000000000000000000000000000000000001000000000000000000000000000000000000000000000000000

result:

ok single line: '001000000000000000000100000000...0000000000000000000000000000000'

Test #45:

score: 0
Accepted
time: 2ms
memory: 4396kb

input:

83 1 51
87 -37
-81 50
92 26
-86 -88
58 47
-57 -37
-81 -32
-38 -55
-78 79
14 50
90 34
24 46
-44 24
57 26
48 -55
-41 -4
84 -38
-5 -66
82 -70
39 92
-47 -71
54 30
-61 -36
59 3
-58 -24
-46 25
36 79
-67 9
-14 67
-67 73
-74 -67
76 -31
-52 90
-9 20
-89 52
64 -27
-13 3
-57 83
-39 41
55 -47
62 5
88 -89
77 -79...

output:

111111010111111111110111011111111111101111110110111

result:

ok single line: '111111010111111111110111011111111111101111110110111'

Test #46:

score: 0
Accepted
time: 1ms
memory: 4396kb

input:

34 51 45
-38 9
-5 -35
-16 -6
-8 28
-28 -42
39 -29
36 -6
-28 -1
39 -17
-16 4
6 -5
-29 38
30 -9
-29 -19
15 14
27 26
6 26
-40 38
30 -29
37 -44
-5 8
-19 11
13 31
-23 28
-42 -15
31 4
-17 43
-3 34
-17 39
25 -39
-40 42
-30 40
-32 -15
-26 -12
-36 -6
35 41
-31 -15
-17 -6
10 24
14 -36
11 37
41 -43
-4 -28
5 -3...

output:

111111111111111111111111111111111001111111011

result:

ok single line: '111111111111111111111111111111111001111111011'

Test #47:

score: 0
Accepted
time: 3ms
memory: 4424kb

input:

99 46 123
-592182435 -645809554
92283434 -714819045
-423525473 -164302428
475848582 -412025661
-536332323 697460306
198041990 258905077
283984406 127967289
-617604502 582772298
-699941320 -230163014
-710474304 -222084831
394078090 -730012818
-477075045 77739018
325949099 -371309760
572486929 -338912...

output:

111111101111110111111110101111110111111110111111111010011110111011110111111110111111011101011100111111111100100000111110111

result:

ok single line: '111111101111110111111110101111...1100111111111100100000111110111'

Test #48:

score: 0
Accepted
time: 2ms
memory: 4432kb

input:

96 54 270
-92 62
-1 24
-54 58
-6 54
-58 66
83 -55
-30 -80
71 54
68 35
-23 -8
0 -38
73 66
49 -56
-71 87
-20 105
-25 -32
106 53
-16 -97
31 -30
-75 28
25 -84
2 13
-31 3
15 22
99 -6
-78 95
32 -57
64 1
24 38
-11 24
38 -20
20 -59
71 28
40 5
-8 70
89 94
54 -60
50 0
-70 29
-40 99
-53 46
-17 3
90 -26
-4 -20
...

output:

111000011000010011011000111000001110101011100011100111000000100111101100010010000010000000000000100100000001011010001110011010101101001001010001000010100101011000001100000100011101100101000111011110000011010111000000000010000010011000001010000001000110001001101100001101

result:

ok single line: '111000011000010011011000111000...0000001000110001001101100001101'

Test #49:

score: 0
Accepted
time: 1ms
memory: 4312kb

input:

51 1 31
-92370944 -764113248
692325784 -851433764
-96851584 824901875
390848076 761934344
-413030187 -898297145
-171510577 841381560
233016216 422104783
721487331 -481096520
871381319 -715381491
-172785176 -411474589
694130790 -210954359
198576848 -682804186
759565175 -146802975
-505077293 -41499702...

output:

1111111111111111111111111111111

result:

ok single line: '1111111111111111111111111111111'

Test #50:

score: 0
Accepted
time: 1ms
memory: 4372kb

input:

32 95 1
245177609 199504310
90689086 -175898276
179952610 -177411595
10121423 -177583648
-62422073 -9211145
-157720737 -177578288
-37542857 224562278
30116853 81612384
-184921179 234707204
123542122 8971776
-164051213 -68266830
144538639 -50285622
704052 -51042388
-92307305 -92629769
132984052 -2274...

output:

1

result:

ok single line: '1'