Submission #550112

#	Time	Username	Problem	Language	Result	Execution time	Memory
550112		fcmalkcin	The Collection Game (BOI21_swaps)	C++17	0 / 100	2 ms	464 KiB

swaps

#include "swaps.h"


#include<bits/stdc++.h>
using namespace std;

#define ll int
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
#define pb push_back
#define F(i,a,b) for(ll i=a;i<=b;i++)

const ll maxn=3e5+10 ;
const ll base=1e9;
const ll mod= 1e9+7 ;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

/// have medal in APIO
/// goal 2/8

ll len;
ll cnt=0;
vector<pll> vt;
map<pll,ll> mp;
ll a[maxn];
ll b[maxn];

void get()
{
   vector<ll> vt1=visit();
   for (int t=0;t<vt1.size();t++)
   {
       mp[vt[t]]=vt1[t];
   }
   vt.clear();
}
void setup(ll x, ll y)
{
   if (x<=len&&y<=len)
   {
       schedule(x,y);
       vt.pb(make_pair(x,y));
   }
   else
   {
        if (x>len&&y>len)
        {
            mp[make_pair(x,y)]=(x>y);
        }
        else if (x>len)
        {
            mp[make_pair(x,y)]=0;
        }
        else
        {
            mp[make_pair(x,y)]=1;
        }
   }
}
void ans(vector<ll> vt)
{
     answer(vt);
}
void solve(ll n,ll v)
{
   ll p=1;
   while (p<n) p*=2;
   len=n;
   vector<ll> vt;
   for (int t=1;t<=p;t++) vt.pb(t);
   for (int t=2;t<=p;t*=2)
   {
       vector<vector<ll>> vt1;
       for (int i=1;i<=p;i+=t)
       {
           vector<ll> vt2;
           for (int k=i;k<=i+t-1;k++)
           {
               vt2.pb(vt[k-1]);
           }
           vt1.pb(vt2);
       }
       while (vt1[0].size()!=1)
       {
           mp.clear();
           for (auto p:vt1)
           {
               ll len=p.size();
               for (int i=0;i<len/2;i++)
               {
                   setup(p[i],p[len-i-1]);
               }
           }
           get();
           vector<vector<ll>> vt2;
           for (auto p1:vt1)
           {
               vector<ll> p=p1;
               for (int i=0;i<len/2;i++)
               {
                   if (mp[make_pair(p[i],p[len-i-1])]==0) swap(p[i],p[len-i-1]);
               }
               vector<ll> vtnxt1;
               vector<ll> vtnxt2;
               for (int i=0;i<len/2;i++)
               {
                   vtnxt1.pb(p[i]);
               }
               for (int i=len/2;i<len;i++)
               {
                   vtnxt2.pb(p[i]);
               }
               vt2.pb(vtnxt1);
               vt2.pb(vtnxt2);
           }
           swap(vt1,vt2);
       }
       vt.clear();
       for (auto p:vt1)
       {
           vt.pb(p[0]);
       }
   }
   vector<ll> res;
   for (int i=0;i<n;i++) res.pb(vt[i]);
   ans(res);
}

/*int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("test.inp","r"))
    {
        freopen("test.inp","r",stdin);
        freopen("test.out","w",stdout);
    }
}*/

Compilation message (stderr)

swaps.cpp: In function 'void get()':
swaps.cpp:34:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |    for (int t=0;t<vt1.size();t++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 3
• Subtask 4: 0 / 2
• Subtask 5: 0 / 9
• Subtask 6: 0 / 6
• Subtask 7: 0 / 9
• Subtask 8: 0 / 6
• Subtask 9: 0 / 21
• Subtask 10: 0 / 14
• Subtask 11: 0 / 9
• Subtask 12: 0 / 6