oj.uz

Submission #991553

# Submission time Handle Problem Language Result Execution time Memory
991553 2024-06-02T12:13:54 Z Yazan_SA Magic Show (APIO24_show) C++17
0 / 100
 13 ms 12228 KB 
#include <bits/stdc++.h>
#include "Alice.h"
using namespace std;

string tob(long long x)
{
    string a="";
    while(x)
    {
        (x%2 ? a+="1" : a+="0");
        x/=2;
    }
    return a;
}
std::vector<std::pair<int,int>> Alice(){
    int n=4999;
    long long x = setN(5000);
    std::vector<std::pair<int,int>>all(n);
    for(int i=0; i<n; i++)
    {
        all[i]={i+1,0};
    }
     all[4998]={4999,5000};

    string b=tob(x);
    int md=(int)b.size();
    for(int i=0; i<n-2; i+=md+1)
    {
        all[i]={all[i].first,md};
    }
    md++;
    for(int i=0; i<(n-2)/md; i++)
    {
        for(int j=0; j<(int)b.size(); j++)
        {
            all[i*md+j+1]={all[i*md+j+1].first,(b[j]=='0'?4999:5000)};
        }
    }
	for(auto &c:all)
	{
		if(c.second==0)c.second=(int)b.size();
        if(c.first==0)c.first=(int)b.size();
	}
    return all;
}

#include <bits/stdc++.h>
#include "Bob.h"
using namespace std;
long long mod=1e18+5;
int pw(long long a, long long b){long long c=1;while(b){if(b%2){c*=a;c%=mod;}a*=a;a%=mod;b/=2;}return c;}


long long bto(string s)
{
    long long ans=0;
    for(long long i=0; i<(int)s.size(); i++)
    {
        (s[i]=='1'?ans+=pw(2,i):ans+=0ll);
    }
    return ans;
}

long long Bob(std::vector<std::pair<int,int>> V){

	int md;
    int n=4999;
    map<int,int>mp;
    vector<int>fr(5000);
    for(auto c:V)
    {
        mp[c.first]=c.second;
        if(c.first==4999 || c.second==5000 || c.first==5000 || c.second==4999)continue;
        fr[c.first]++;
        fr[c.second]++;
    }
    int mx=0;
    for(int i=0; i<5000; i++)
    {
        if(fr[i]>mx)md=i,mx=fr[i];
    }

    md++;
    string s=string(md-1,'3');

    for(int j=0; j<md; j++)
    {
        for(int i=0; i<(n-2)/md; i++)
        {
            if(mp[i*md+j+1]==4999)
            {
                s[j-1]='0';
                break;
            }
            if(mp[i*md+j+1]==5000)
            {
                s[j-1]='1';
                break;
            }
        }
    }

    return bto(s);
}

Compilation message

Bob.cpp: In function 'long long int Bob(std::vector<std::pair<int, int> >)':
Bob.cpp:20:6: warning: 'md' may be used uninitialized in this function [-Wmaybe-uninitialized]
   20 |  int md;
      |      ^~

Subtask #1
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1076 KB Correct.
2 Incorrect 13 ms 12228 KB Incorrect answer.
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1076 KB Correct.
2 Incorrect 13 ms 12228 KB Incorrect answer.
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1076 KB Correct.
2 Incorrect 13 ms 12228 KB Incorrect answer.
3 Halted 0 ms 0 KB -