QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#287954#4209. Stranded Far From HomeMax_s_xaM100 ✓68ms45812kbC++144.0kb2023-12-21 12:46:432023-12-21 12:46:45

Judging History

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

  • [2023-12-21 12:46:45]
  • 评测
  • 测评结果:100
  • 用时:68ms
  • 内存:45812kb
  • [2023-12-21 12:46:43]
  • 提交

answer

#include <iostream>
#include <algorithm>
#include <vector>

typedef long long ll;
typedef double lf;

// #define DEBUG 1
struct IO
{
    #define MAXSIZE (1 << 20)
    #define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    #if DEBUG
    #else
    IO() : p1(buf), p2(buf), pp(pbuf) {}
    ~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
    #endif
    #define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
    #define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')

    template <typename T>
    void Read(T &x)
    {
        #if DEBUG
        std::cin >> x;
        #else
        bool sign = 0; char ch = gc(); x = 0;
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
        if (sign) x = -x;
        #endif
    }
    void Read(char *s)
    {
        #if DEBUG
        std::cin >> s;
        #else
        char ch = gc();
        for (; blank(ch); ch = gc());
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
        #endif
    }
    void Read(char &c) {for (c = gc(); blank(c); c = gc());}

    void Push(const char &c)
    {
        #if DEBUG
        putchar(c);
        #else
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
        #endif
    }
    template <typename T>
    void Write(T x)
    {
        if (x < 0) x = -x, Push('-');
        static T sta[35];
        int top = 0;
        do sta[top++] = x % 10, x /= 10; while (x);
        while (top) Push(sta[--top] ^ 48);
    }
    template <typename T>
    void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)

using namespace std;

const int MAXN = 2e5 + 10;

int n, m, odr[MAXN], idx[MAXN];
bool ans[MAXN];
ll s[MAXN];
vector <int> e[MAXN], re[MAXN];

int fa[MAXN];
vector <int> res[MAXN];
bool avl[MAXN];
int Find(int k) {return k == fa[k] ? k : fa[k] = Find(fa[k]);}
inline void Union(int u, int v)
{
    u = Find(u), v = Find(v);
    if (u == v) return;
    if (res[u].size() < res[v].size()) swap(u, v);
    fa[v] = u, s[u] += s[v];
    for (auto x : res[v]) res[u].push_back(x);
}
inline void Union2(int u, int v)
{
    u = Find(u), v = Find(v);
    if (u == v) return;
    fa[v] = u, s[u] += s[v];
}

int main()
{
    // freopen("B.in", "r", stdin);
    // freopen("B.out", "w", stdout);
    #if DEBUG
    #else
    ios::sync_with_stdio(0), cin.tie(0);
    #endif
    Read(n), Read(m);
    for (int i = 1; i <= n; i++) Read(s[i]), odr[i] = i;
    sort(odr + 1, odr + n + 1, [&](int x, int y) {return s[x] < s[y];});
    for (int i = 1; i <= n; i++) idx[odr[i]] = i;
    for (int i = 1, u, v; i <= m; i++)
    {
        Read(u), Read(v);
        if (idx[u] < idx[v]) swap(u, v);
        e[u].push_back(v), re[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) fa[i] = i, res[i].push_back(i);
    for (int i = 1; i <= n; i++)
    {
        int u = odr[i];
        // cout << u << "\n";
        for (auto v : e[u])
        {
            if (Find(u) == Find(v)) continue;
            // cout << u << ' ' << v << " E\n";
            // cout << s[Find(v)] << " " << s[Find(u)] << "\n";
            if (s[Find(v)] >= s[Find(u)]) avl[v] = 1;
        }
        for (auto v : e[u])
        {
            if (Find(u) == Find(v)) {avl[v] = 0; continue;}
            if (avl[v]) Union(u, v), avl[v] = 0;//, cout << u << " " << v << " #\n";
            else Union2(u, v);
        }
        // for (int j = 1; j <= n; j++, cout << "\n")
        // {
        //     cout << j << " " << s[j] << ":\n";
        //     for (auto x : res[j]) cout << x << ' ';
        // }
            
        // cout << "\n";
    }
    for (auto x : res[Find(odr[n])]) ans[x] = 1;
    for (int i = 1; i <= n; i++) cout << ans[i];
    return 0;
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 0ms
memory: 22160kb

input:

1622 1998
29021716 740464354 721037601 759718475 973636178 59068917 294028640 285332651 203821680 397646208 488684783 448548424 565347277 112938323 832704692 837437153 508335516 167646888 798998153 86605661 820823253 705498382 116513873 672806499 522392461 568294614 457655230 647498964 577669416 506...

output:

011110101110001100101101111110010100010010000100100110111010111010110011111100011110111001001111011001111010111001110111111101111100110110100111001011110101011101101111100111110000111100010011010011100111010101001111111110000101001111011111011101110000101010001011001111110111110001101111101010101011...

result:

ok single line: '011110101110001100101101111110...1000100110101000000111111011011'

Test #2:

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

input:

2000 2000
864098683 591498712 213777486 59204290 934602516 58889078 651710816 522455089 109288143 369477344 245457117 508405213 300100362 824363920 223504153 262425016 942079572 679044734 459712786 240267388 479578710 756403013 605605067 373934824 394989986 71007490 989717606 324816874 694848141 967...

output:

010000110101110111001011001001100011011011111010111101010010010110011111111001100011001110010110101001001100101110101011110110101110001110100101110110111110110110101111111110111100100010100011010101100001100111111011101001110101010000110010011011000000110101111010010100011111100101100011011101101010...

result:

ok single line: '010000110101110111001011001001...1001011101110101011010110101000'

Test #3:

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

input:

1 0
1

output:

1

result:

ok single line: '1'

Test #4:

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

input:

2000 1999
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok single line: '000000000000000000000000000000...0000000000000000000000000000001'

Test #5:

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

input:

2000 1999
206944287 446302790 101145912 408233897 297550532 862460985 297550532 434100957 604346912 853067713 745085291 823763956 206248832 515603549 595281048 81583217 371459366 93952980 96198386 310603764 614551757 894430957 71853228 509766586 630983372 318906450 388499992 819471794 38199178 47218...

output:

010101011101011010011100101100011010101000100010110110010111010001100110101010110110111011010101101110110101001100101101010100101101101100110101101101110000111011011011010110110100110011010101010101101111100101011011011010011011001011010110101010110110011001100101010110111010101100101010010010001111...

result:

ok single line: '010101011101011010011100101100...1011010011011001000101010010001'

Test #6:

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

input:

1345 1789
375167482 503306237 315868237 266756331 949398152 741681679 543655906 174472929 410442643 715616210 456387310 951728541 801716815 245590232 338015269 431597716 920266757 550723739 58977132 529933211 578064018 278767845 968148205 408029700 719289452 335374052 828528189 51196184 29650216 705...

output:

110011001111100011011011101001110110000111111111110100111101011000001010111010110100111101110111110110111000011111100011101111101010101011011111001100011111001011111100011111110101101100011100111000111110001001100011110101010001010100000011111010110011001001100110000011110110111110110111111011110110...

result:

ok single line: '110011001111100011011011101001...1100110111011110110011110010011'

Test #7:

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

input:

1500 2000
701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 701816859 ...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111100'

Test #8:

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

input:

1999 1998
999452824 999324574 999290252 998151340 998105039 997146818 996813715 995247573 994565865 994546928 993167552 993167552 993167552 993167552 993167552 993167552 993167551 993167551 993167551 993167551 993167551 993167551 993167551 993167551 993167551 993167551 993167551 993167551 993167551 ...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #9:

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

input:

1987 1986
261869662 831577244 618973318 468200895 246536438 845676833 56390992 19216037 787915057 128807420 655287042 130266510 610809981 478890008 359959522 537679987 818419751 359573232 733007587 717716502 746480782 63050741 900099232 170056139 83295618 984934788 915216270 766905004 778868217 7799...

output:

011101001010110110101010011011111101001100101010101001011010110101100001010110000100111011011001001011001100100101101110011010101101011101001110111100111010101101110111111010101001011010001101101101000100110010100110010110100111010110101111010101100011010111011011001001101110010011010110001101110110...

result:

ok single line: '011101001010110110101010011011...1011011101010110101011001101100'

Test #10:

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

input:

1700 2000
428947253 736462289 319157085 727475665 972488764 283807601 684489299 81745926 144166353 536066145 85873104 987105557 594373272 380940752 237478178 787584189 920011214 379319524 907136486 389717089 857220208 41641816 922205476 298642596 381750550 930207009 207115349 516168870 430828954 857...

output:

011111100101010111101010110101111111100000101111011001010101111111110011100110001000100010101101011110000111101111011101111001011010000010010101111111101111000101001111110011111101001100010010111001110101001001001110011011001111111101110100111011010111101011110001111110110011011110110110101100011111...

result:

ok single line: '011111100101010111101010110101...0100110001111011000100100011100'

Test #11:

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

input:

2000 1999
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 100000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

000000000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok single line: '000000000000000000000000000000...0000000000000000000000000000000'

Test #12:

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

input:

2000 1999
964007777 1 605413025 164784195 3 715902366 3 634775847 941695128 1 420368641 3 2 1 297974801 1 3 578313437 1 3 1 143818383 3 3 437065119 155017860 2 3 868128308 405696073 235953771 311748137 2 2 2 888698361 2 3 2 534499205 2 2 2 177807108 418037485 2 2 223058634 321555136 3 3 2 800197199 ...

output:

101101011010001001000100100011110001000100011001100011000111010000010100010110101011001100001000000101000110001000110011010010101001001100111001010100100011001001001001101010010100100000000001001010000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok single line: '101101011010001001000100100011...0000000000000000000000000000000'

Test #13:

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

input:

4 4
2 2 4 3
1 2
1 3
2 3
3 4

output:

1110

result:

ok single line: '1110'

Test #14:

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

input:

4 3
4 2 2 1
1 2
3 2
4 1

output:

1110

result:

ok single line: '1110'

Subtask #2:

score: 10
Accepted

Test #15:

score: 10
Accepted
time: 50ms
memory: 45180kb

input:

200000 199999
100000000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok single line: '100000000000000000000000000000...0000000000000000000000000000000'

Test #16:

score: 0
Accepted
time: 42ms
memory: 42892kb

input:

200000 199999
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #17:

score: 0
Accepted
time: 51ms
memory: 39248kb

input:

200000 199999
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #18:

score: 0
Accepted
time: 29ms
memory: 42244kb

input:

197865 197864
999999999 197864 197863 197862 197861 197860 197859 197858 197857 197856 197855 197854 197853 197852 197851 197850 197849 197848 197847 197846 197845 197844 197843 197842 197841 197840 197839 197838 197837 197836 197835 197834 197833 197832 197831 197830 197829 197828 197827 197826 197...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111110'

Test #19:

score: 0
Accepted
time: 43ms
memory: 39244kb

input:

200000 199999
394734328 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734327 394734...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #20:

score: 0
Accepted
time: 47ms
memory: 40496kb

input:

200000 199999
999999209 999998104 999990842 999977349 999967647 999953886 999944346 999937923 999933492 999930655 999930025 999927140 999922019 999901883 999877304 999862203 999860267 999855746 999852885 999843366 999841686 999834454 999829798 999818121 999816339 999795375 999792758 999789141 999787...

output:

101110111101111011101110100011100110111101011001111111011011011001110111010111000111000111010011111110100110111110111011111100111101110101111011111111011011111001011110110010110101101101101101101011001111011101110111101101011101111011101010011001111101110111110110111100111011111111100111110101111111...

result:

ok single line: '101110111101111011101110100011...1010011011101111111101111101000'

Test #21:

score: 0
Accepted
time: 24ms
memory: 38164kb

input:

200000 199999
43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 43308787 4330878...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111100'

Test #22:

score: 0
Accepted
time: 55ms
memory: 42716kb

input:

199454 199453
999998640 999997136 999987625 999952089 999939037 999922249 999921857 999917112 999914336 999907965 999906695 999903007 999896323 999879887 999877394 999868697 999853093 999844638 999835558 999824290 999818023 999816299 999805495 999798018 999788813 999777075 999762348 999756962 999751...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #23:

score: 0
Accepted
time: 45ms
memory: 45812kb

input:

200000 199999
990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324646 990324...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111110'

Test #24:

score: 0
Accepted
time: 50ms
memory: 44932kb

input:

200000 199999
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 ...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #25:

score: 0
Accepted
time: 49ms
memory: 41396kb

input:

193456 193455
999976400 999973235 999965887 999956575 999954856 999946458 999939374 999933024 999931055 999930598 999925073 999908651 999906000 999903969 999902743 999900117 999878112 999875576 999871511 999865306 999859582 999854429 999847171 999841447 999832498 999831093 999820334 999816726 999802...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #26:

score: 0
Accepted
time: 25ms
memory: 35804kb

input:

199998 199997
999998264 999997294 999985088 999974097 999971316 999958519 999957274 999951713 999950923 999948846 999946625 999930732 999922264 999921246 999916016 999914065 999911360 999906253 999901430 999900748 999897291 999878722 999862790 999852746 999842642 999838338 999810090 999804174 999801...

output:

110000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok single line: '110000000000000000000000000000...0000000000000000000000000000000'

Test #27:

score: 0
Accepted
time: 40ms
memory: 42352kb

input:

199999 199998
999999608 999992754 999987992 999976690 999966194 999966001 999955134 999952859 999951255 999922335 999921620 999911687 999909360 999907128 999881599 999879187 999877305 999866676 999864468 999862695 999860720 999856633 999854113 999846437 999845437 999840212 999838306 999835644 999826...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Test #28:

score: 0
Accepted
time: 41ms
memory: 42440kb

input:

200000 199999
999999039 999992847 999989031 999987682 999981641 999971744 999961497 999961484 999960563 999959000 999951299 999949456 999942242 999934797 999933717 999927670 999926557 999926480 999906047 999903935 999900062 999899222 999877270 999866504 999859399 999859010 999845971 999844273 999843...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111110'

Test #29:

score: 0
Accepted
time: 50ms
memory: 41984kb

input:

200000 199999
999999709 999999162 999994754 999991149 999985824 999983538 999976018 999968620 999964108 999961015 999951735 999947137 999930936 999928294 999923485 999917026 999912909 999906378 999900558 999880696 999877175 999870121 999866512 999861100 999857145 999856638 999853948 999850156 999829...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...0000000000000000000000000000000'

Subtask #3:

score: 15
Accepted

Test #30:

score: 15
Accepted
time: 57ms
memory: 42452kb

input:

199999 199998
758475118 758475116 758475114 758475112 758475110 758475108 758475106 758475104 758475102 758475100 758475098 758475096 758475094 758475092 758475090 758475088 758475086 758475084 758475082 758475080 758475078 758475076 758475074 758475072 758475070 758475068 758475066 758475064 758475...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #31:

score: 0
Accepted
time: 61ms
memory: 40820kb

input:

198765 198764
331155986 402813770 954736614 79847944 642540167 755767778 749263519 200053132 274136233 631137603 175636207 109779934 886611000 234477496 562265730 302427246 297486401 72574701 921718778 740910704 341000613 985634966 75658269 782951356 920385380 798515520 757586463 121205584 268860640...

output:

001001100100101110110100111001000111101011110010010010011110011110010100101101100101110101010110110111001101001011011010101001001011101000101010011010101110011001010010101001011101101101101110001011111010100101010100010101001110100101101001110100110101101100110101110101110101010101100011100001110011...

result:

ok single line: '001001100100101110110100111001...0100010100100101101101111011011'

Test #32:

score: 0
Accepted
time: 44ms
memory: 45284kb

input:

200000 199999
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok single line: '000000000000000000000000000000...0000000000000000000000000000000'

Test #33:

score: 0
Accepted
time: 66ms
memory: 41068kb

input:

200000 199999
973782915 35648972 172596522 601896399 657615106 720871531 976214509 446111696 189618206 399911908 892223392 369847507 486921791 70613624 777025377 517806930 173932492 756397069 562347260 424838009 679282612 700671799 538116557 677185500 610575497 56830539 61584658 542652772 166440288 ...

output:

100111110110101001101101100101101100110100101011010100101110111011010111110010101010011000111010101010000010110110100110111011010110011100101001011100011011101100010101101001011011011110110110010011000001011010101000111000110110101110111011101100001000011011110110111011001011011011011100101011001101...

result:

ok single line: '100111110110101001101101100101...0101010010010101001111011011010'

Test #34:

score: 0
Accepted
time: 55ms
memory: 40668kb

input:

200000 199999
345405829 2 109769187 2 1 490612702 2 244832428 3 2 419221331 1 366178257 1 2 532464052 1 301316374 321824777 2 717352787 1 876791004 1 1 2 616251348 1 1 704374710 1 1 3 272971488 3 3 1 963539338 1 3 2 724905843 482091358 2 317344438 2 1 394153708 596255371 2 1 2 120533108 3 2 1 856214...

output:

000001000010000100101010000001000000010001100001100000001000010001010000000100000100010001000010001010001000001010001000000100010000100010100010010000100000001001000000001010010001001000100001010100001000010000100000101000000001000000010010100010010010000000100010100000011000000001000001001000010010...

result:

ok single line: '000001000010000100101010000001...0000000000000000000000000000000'

Test #35:

score: 0
Accepted
time: 45ms
memory: 42292kb

input:

199999 199998
758475117 758475115 758475113 758475111 758475109 758475107 758475105 758475103 758475101 758475099 758475097 758475095 758475093 758475091 758475089 758475087 758475085 758475083 758475081 758475079 758475077 758475075 758475073 758475071 758475069 758475067 758475065 758475063 758475...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #36:

score: 0
Accepted
time: 48ms
memory: 37136kb

input:

200000 199999
1000000000 100000 1 100000 2 100000 3 100000 4 100000 5 100000 6 100000 7 100000 8 100000 9 100000 10 100000 11 100000 12 100000 13 100000 14 100000 15 100000 16 100000 17 100000 18 100000 19 100000 20 100000 21 100000 22 100000 23 100000 24 100000 25 100000 26 100000 27 100000 28 1000...

output:

110101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...

result:

ok single line: '110101010101010101010101010101...1010101010101010101010101010101'

Test #37:

score: 0
Accepted
time: 64ms
memory: 41072kb

input:

200000 199999
718929573 717111089 992199381 626261244 906555145 388488932 345739070 106595293 679494970 244317698 14700848 554411121 476144448 110764162 736567729 713168823 60052623 446221816 902980237 308525368 717595171 460839947 574455487 315606085 915162653 384642849 325014015 500035847 63956531...

output:

101011101001101100101010110111101010101011110101101010101101000101011001010101010111110011110110100101011011110101111010011011001011101011100010010101110110010111001100010010001010010101010101100010011001001110110101011011010011011101010100001101100110101101111101011001011000100011011001110000101001...

result:

ok single line: '101011101001101100101010110111...1011010110100111001100010011000'

Test #38:

score: 0
Accepted
time: 59ms
memory: 41648kb

input:

200000 199999
999999998 2 3 999999998 999999998 2 2 2 999999996 2 3 2 1000000000 2 2 2 999999998 999999996 1 3 999999996 2 1000000000 3 999999997 1 1 999999998 3 999999998 2 999999996 1 999999996 1 2 1000000000 1000000000 1 999999997 999999997 1 3 3 999999998 2 999999997 1 2 2 999999998 999999998 1 ...

output:

100110001000100011001010100101010100110110001010001100101000100100010001001000110100010010010010110001000111011010001001100100010011000101010101010110010001000101000101110001010011001001010001100010101001001010110100101001110010010011000101100010010100010010001010010100010001010101000101100011000100...

result:

ok single line: '100110001000100011001010100101...0000000000000000000000000000000'

Subtask #4:

score: 30
Accepted

Test #39:

score: 30
Accepted
time: 45ms
memory: 35740kb

input:

155555 200000
473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735421 473735...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111100'

Test #40:

score: 0
Accepted
time: 60ms
memory: 40060kb

input:

200000 200000
913658453 969766488 685576437 527887525 685576437 495438734 959695974 527887525 913658453 618257806 959695974 959695974 969766488 618257806 90942432 969766488 969766488 527887525 913658453 685576437 913658453 959695974 685576437 495438734 90942432 809500728 809500728 959695974 96976648...

output:

111011101111100010111100001111111101111100110000011111100111111101010110010010111101110001100111011101000111000111111111110011100011100101100110001111000101101111111101100100110111111111110111011101110101101001000111011101011110001011101011111111100001000111111011111111000101110110001100111011110011...

result:

ok single line: '111011101111100010111100001111...0101010111010110010000010101110'

Test #41:

score: 0
Accepted
time: 60ms
memory: 40604kb

input:

199199 199277
289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252171 289252...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111100'

Test #42:

score: 0
Accepted
time: 40ms
memory: 31620kb

input:

100000 199999
2 1 37485 37485 2 37485 6 5 1 6 37485 4 4 6 3 2 37485 6 1 3 4 37485 37485 37485 4 6 2 37485 6 4 3 37485 2 5 37485 2 5 3 6 6 1 1 2 1 2 1 4 37485 1 37485 2 2 2 2 1 6 3 6 5 2 6 3 4 1 2 37485 5 3 5 5 3 4 1 2 37485 2 4 6 1 6 37485 4 1 5 37485 37485 2 37485 2 3 1 6 2 1 2 1 5 4 6 5 3 2 3 4 6 ...

output:

001101000010000010000111000100010010000000000001010000000000000001000000001000001000110100000000000000000000100000001001001010001101000001100010000000000001000100000000000100001011100010010010000001000000000000000000010001000100001011100001000000000011110000000001000100000000000100000000000000000101...

result:

ok single line: '001101000010000010000111000100...0011100010010000001000000110000'

Test #43:

score: 0
Accepted
time: 47ms
memory: 37660kb

input:

200000 199999
860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372385 860372...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #44:

score: 0
Accepted
time: 59ms
memory: 42080kb

input:

200000 199999
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok single line: '000000000000000000000000000000...0000000000000000000000000000000'

Test #45:

score: 0
Accepted
time: 52ms
memory: 38392kb

input:

189878 196660
775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107700 775107...

output:

111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111111111111111111111111111111'

Test #46:

score: 0
Accepted
time: 68ms
memory: 38812kb

input:

198765 200000
29315757 26509418 255031982 938155695 955741123 789077519 877029199 789077519 939894014 877029199 877029199 939894014 255031982 255031982 955741123 939894014 791418156 26509418 939894014 255031982 717440373 789077519 938155695 789077519 877029199 789077519 955741123 877029199 789077519...

output:

000111011101001110100110111111111011011111000100111101101111111010011100010001101100111111101110011100100111100000110010111011010101000111011111011111110000101101111001111110001001110110101111011110001111000101100111000111111001111010000011001001101110110101011110101100101111100011011111111011001001...

result:

ok single line: '000111011101001110100110111111...1000011101111010100110011000000'

Test #47:

score: 0
Accepted
time: 34ms
memory: 40872kb

input:

200000 199999
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...

output:

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

result:

ok single line: '000000000000000000000000000000...1111111111111111111111111111111'

Test #48:

score: 0
Accepted
time: 60ms
memory: 38848kb

input:

198765 198899
947284576 877865720 2015967 401645128 993427684 877865720 877865720 825858906 433421421 825858906 352548281 993427684 401645128 877865720 993427684 401645128 401645128 125204623 2015967 822297788 947284576 125204623 2015967 2015967 947284576 2015967 993427684 993427684 2015967 82585890...

output:

110111111101111000001000001101111000001100110111100010011101101101110000110110101010001110010101111101101000110011011110011011011011100110100001010001100110101110011010100111010011111111110011110101111111011101111111000011101010001010001001111100001100010110101101011110111100110010111101111011110011...

result:

ok single line: '110111111101111000001000001101...1101001001101101001110111100110'

Subtask #5:

score: 35
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Test #49:

score: 35
Accepted
time: 10ms
memory: 25748kb

input:

4000 200000
496463018 100404795 559533461 699900587 369647814 29718432 40894608 68408954 514011434 548459384 946824736 334321620 663677318 432856491 559533462 865854007 738910069 59436862 116873625 493445205 695195074 854404086 527531257 599796404 451191308 923432792 423131746 934340669 436439899 70...

output:

111111111111111111111111111111111111111111111111111111111111111011111111011111111111111111111111111111111111111111111111111111111111111111111110111111111111111111011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

result:

ok single line: '111111111111111111111111111111...1111101111111111111111111111111'

Test #50:

score: 0
Accepted
time: 62ms
memory: 35708kb

input:

166666 200000
706298411 662315621 40705755 825389758 251378579 442576099 73729656 784021484 986276402 650586940 911992856 640633085 151045478 530676995 722599914 594796064 746198288 143815813 993884395 742463197 473894261 697043822 526073174 363446082 410846697 665027722 528462346 352511628 16355170...

output:

110001011111001110110111111001111100000101100000001010111011111111101110011110010101011011011111100111111111000110011010100101011101010110011011100000101101010100100110111010101110111101100101110011111101100110011101111011110110101011101010101001101111110101010010111001010001100101101101010000011111...

result:

ok single line: '110001011111001110110111111001...1010111111010100001010100011011'

Test #51:

score: 0
Accepted
time: 66ms
memory: 38464kb

input:

195678 200000
550446285 481307825 990536038 735185703 52339625 885213081 846313971 640355278 527045562 573786788 913468273 868540688 401057730 105710959 385417404 911896779 219887272 612874029 13500913 396298120 971233203 961486646 3011008 754965098 687345650 429621727 323149854 369201678 250375444 ...

output:

111101111011100111011100101011110111001111111111100000100011110011101000101001101011100101011111010110100100011110011111010011010111000110111100111111100011101101101001100101010010110111100010110111011110010011110101111011001111011100011000111101100100110011110110100011110110110111010000101100110001...

result:

ok single line: '111101111011100111011100101011...1000100010101101000000100010110'

Test #52:

score: 0
Accepted
time: 63ms
memory: 39512kb

input:

200000 200000
289156681 663136039 898734055 737503360 986909741 963264673 852751734 281043006 646893972 261392323 459107718 817787106 82179280 526649862 413280443 968239421 657990078 915555721 258673328 221978936 389062182 21050632 733739893 194878167 354540623 643995820 687588587 391820050 41762535...

output:

011111101101011101010010111100111011100010011101000000000110111001101011001101111001100010100110000000111011110110001101010110010101110100100111010011110010101010111110000111101111000000011101011001000110010101100100101011110111001111100101010100001100100011110110100110100011110111011001100100011010...

result:

ok single line: '011111101101011101010010111100...0000100010111010011111000011011'