QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#83626 | #5528. Least Annoying Constructive Problem | Crysfly | WA | 2ms | 3368kb | C++17 | 1.4kb | 2023-03-02 19:24:25 | 2023-03-02 19:24:26 |
Judging History
answer
// what is matter? never mind.
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define ull unsigned long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
if(f)x=-x;return x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 400005
#define inf 0x3f3f3f3f
int n,m,a[505][505];
pii e[maxn];
void sol0()
{
For(i,1,n-1){
a[i][n]=a[n][i]=(i-1)*(n/2)+1;
int l=i,r=i;
For(j,2,n/2){
--l,++r;
if(l==0)l=n-1;
if(r==n)r=1;
a[l][r]=a[r][l]=(i-1)*(n/2)+j;
}
}
m=n*(n-1)/2;
For(i,1,n)For(j,i+1,n)e[a[i][j]]=mkp(i,j);
}
void sol1()
{
int i=1;
For(_,1,n){
int l=i,r=i+1;
if(r==n+1)r=1;
For(__,1,n/2){
e[++m]=mkp(l,r);
--l,++r;
if(l==0)l=n;
if(r==n+1)r=1;
}
i=l;
}
}
int fa[9999];
int gf(int x){
while(x^fa[x])x=fa[x]=fa[fa[x]];
return x;
}
void chk(int l,int r){
For(i,1,n)fa[i]=i;
For(i,l,r){
if(gf(e[i].fi)==gf(e[i].se))assert(0);
fa[gf(e[i].fi)]=gf(e[i].se);
}
}
signed main()
{
n=read();
if(n%2==0)sol0();
else sol1();
For(i,1,m) cout<<e[i].fi<<" "<<e[i].se<<"\n";
For(i,1,m-(n-1)+1) chk(i,i+(n-1)-1);
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3368kb
input:
3
output:
1 2 3 1 2 3
result:
wrong answer Integer 1 violates the range [4, 3]