QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#137118 | #6353. Kth Lex Min Min Min Subpalindromes | berarchegas# | WA | 47ms | 26984kb | C++17 | 5.4kb | 2023-08-09 21:09:56 | 2023-08-09 21:09:58 |
Judging History
answer
#include <algorithm>
#include <deque>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <random>
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef pair<ll,ll> pll;
typedef vector<string> vs;
typedef vector<pll> vpl;
typedef vector<int> vi;
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
const int maxn = 10*100000 + 10;
// const int inf = 1000000000;
// const ll inf = 1000000000000000000LL;
// const ll mod = 998244353;
// const ll mod = 1000000007; // 10^9 + 7
ll n, m, k;
ll pw[maxn];
void printAnswer(vector<ll> v = {})
{
if( v.empty() )
cout << -1 << endl;
else
{
for(int x: v)
cout << x << " ";
cout << endl;
}
exit(0);
}
void dealSmallCases()
{
if( n == 1 )
{
if( k <= m )
printAnswer( { k } );
else
printAnswer();
}
if( m == 1 )
{
if( k == 1 )
printAnswer( vector<ll>(1, n) );
else
printAnswer();
}
if( n == 2 )
{
ll num = m*(m - 1);
if( k <= num )
{
ll a = ((k - 1)/(m - 1)) + 1;
ll b = ((k - 1)%(m - 1)) + 1;
if( b >= a ) b++;
printAnswer( { a , b } );
}
else
printAnswer();
}
}
ll lim;
ll mult(ll a, ll b)
{
if( a > lim || b > lim || a > lim/b )
return lim + 1;
return min( a*b , lim + 1 );
}
void generalCase()
{
pw[0] = 1;
for(int i = 1 ; i <= n ; i++)
pw[i] = mult( pw[i - 1] , m - 2 );
ll numWays = mult( m , m - 1 );
numWays = mult( numWays , pw[n - 2] );
if( numWays < k )
printAnswer();
vector<ll> ans(n);
for(int i = 0 ; i < n ; i++)
{
ll numWaysRemain = pw[n - i - 1];
if( i == 0 ) numWaysRemain = mult( m - 1 , pw[n - 2] );
ans[i] = (k - 1)/numWaysRemain;
k -= ans[i]*numWaysRemain;
ans[i]++;
ll a = (i >= 1) ? ans[i - 1] : m + 1;
ll b = (i >= 2) ? ans[i - 2] : m + 1;
if( ans[i] >= max( a , b ) )
ans[i] += 2;
else if( ans[i] >= min( a , b ) && abs(a - b) == 1 )
ans[i] += 2;
else if( ans[i] >= min( a , b ) )
ans[i]++;
}
printAnswer(ans);
}
bool isPalindrome(vector<ll> v)
{
vector<ll> a = v;
reverse( a.begin() , a.end() );
return (v == a);
}
int numPalindromes(vector<ll> v)
{
int ans = 0;
int n = (int)v.size();
for(int i = 0 ; i < n ; i++)
{
vector<ll> cur = { v[i] };
for(int j = i + 1 ; j < n ; j++)
{
cur.push_back( v[j] );
if( isPalindrome(cur) )
ans++;
}
}
return ans;
}
void binaryArray()
{
if( n < 6 )
{
int minValue = 738242;
vector< vector<ll> > answers;
for(int mask = 0 ; mask < (1 << n) ; mask++)
{
vector<ll> cur(n);
for(int j = 0 ; j < n ; j++)
cur[j] = (mask >> j)%2;
minValue = min( minValue , numPalindromes(cur) );
}
for(int mask = 0 ; mask < (1 << n) ; mask++)
{
vector<ll> cur(n);
for(int j = 0 ; j < n ; j++)
cur[j] = (mask >> j)%2;
for(int j = 0 ; j < n ; j++)
cur[j]++;
if( numPalindromes(cur) == minValue )
answers.push_back( cur );
}
if( k <= (int)answers.size() )
printAnswer( answers[k - 1] );
else
printAnswer();
}
vector< vector<ll> > starts = {
{1, 1, 0, 1, 0, 0},
{1, 0, 1, 1, 0, 0},
{1, 1, 0, 0, 1, 0},
{0, 1, 1, 0, 1, 0},
{1, 0, 0, 1, 1, 0},
{0, 1, 0, 1, 1, 0},
{1, 0, 1, 0, 0, 1},
{0, 1, 1, 0, 0, 1},
{1, 0, 0, 1, 0, 1},
{0, 0, 1, 1, 0, 1},
{0, 1, 0, 0, 1, 1},
{0, 0, 1, 0, 1, 1},
};
sort( starts.begin() , starts.end() );
if( k <= 12 )
{
vector<ll> ans = starts[k - 1];
for(int i = 6 ; i < n ; i++)
ans.push_back( ans[i%6] );
for(int i = 0 ; i < n ; i++)
ans[i]++;
printAnswer(ans);
}
else
printAnswer();
}
void solve(int testcase)
{
cin >> n >> m >> k;
lim = k;
dealSmallCases();
if( m >= 3 )
generalCase();
else
binaryArray();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
for(int testcase = 1 ; testcase <= t ; testcase++)
solve( testcase );
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3540kb
input:
1 1 1
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3536kb
input:
2 2 2
output:
2 1
result:
ok 2 number(s): "2 1"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
3 3 3
output:
2 1 3
result:
ok 3 number(s): "2 1 3"
Test #4:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
9 9 8244353
output:
2 4 1 2 6 8 1 2 7
result:
ok 9 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
10 7 998244353
output:
-1
result:
ok 1 number(s): "-1"
Test #6:
score: 0
Accepted
time: 1ms
memory: 3592kb
input:
3 1000 994253860
output:
998 244 353
result:
ok 3 number(s): "998 244 353"
Test #7:
score: 0
Accepted
time: 1ms
memory: 3520kb
input:
58 4 864691128455135232
output:
4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4 3 2 4
result:
ok 58 numbers
Test #8:
score: 0
Accepted
time: 1ms
memory: 3492kb
input:
58 4 864691128455135233
output:
-1
result:
ok 1 number(s): "-1"
Test #9:
score: 0
Accepted
time: 47ms
memory: 26940kb
input:
1000000 1000000 1000000000000000000
output:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
result:
ok 1000000 numbers
Test #10:
score: -100
Wrong Answer
time: 45ms
memory: 26984kb
input:
1000000 4 1000000000000000000
output:
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ...
result:
wrong answer 999941st numbers differ - expected: '4', found: '3'